{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e这是问题的困难版本。不同之处在于对 $$$n$$$、$$$m$$$ 和 $$$t$$$ 的约束条件。只有当解决了问题的所有版本时,才能进行黑客攻击。\u003c/span\u003e\u003c/p\u003e\u003cp\u003e给出了 Alice 和 Bob 的数字 $$$n$$$、$$$m$$$ 和 $$$k$$$,并按以下方式进行游戏:\u003c/p\u003e\u003cp\u003e游戏有一个分数,Alice 试图最大化,而 Bob 则试图最小化。分数最初为 $$$0$$$。游戏由 $$$n$$$ 轮组成。每一轮,Alice 从 $$$0$$$ 到 $$$k$$$(包括端点)中选择一个 \u003cspan class\u003d\"tex-font-style-bf\"\u003e实数\u003c/span\u003e,Bob 要么将其加到游戏的分数中,要么从中减去。但在整个游戏过程中,Bob 必须选择至少在 $$$n$$$ 轮中添加 $$$m$$$ 个。\u003c/p\u003e\u003cp\u003eBob 在决定是否将数字从游戏分数中添加或减去之前,会知道 Alice 选择了哪个数字,而 Alice 在选择当前轮的数字之前会知道 Bob 在上一轮中是添加还是减去数字(除了第一轮,因为没有上一轮)。\u003c/p\u003e\u003cp\u003e如果 Alice 和 Bob 都采取最佳策略,游戏的最终分数将是多少?\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含一个整数 $$$t$$$($$$1 \\le t \\le 10^5$$$) — 测试用例的数量。接下来是每个测试用例的描述。\u003c/p\u003e\u003cp\u003e每个测试用例包含一行,包含三个整数,$$$n$$$、$$$m$$$ 和 $$$k$$$($$$1 \\le m \\le n \\le 10^6, 0 \\le k \u0026lt; 10^9 + 7$$$) — 轮数、Bob 必须添加的轮数,以及 Alice 可以选择的最大数字。\u003c/p\u003e\u003cp\u003e保证所有测试用例中 $$$n$$$ 的总和不超过 $$$10^6$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试用例,输出一个单独的 \u003cspan class\u003d\"tex-font-style-bf\"\u003e整数\u003c/span\u003e — 最佳游戏的分数对 $$$10^9 + 7$$$ 取模的结果。\u003c/p\u003e\u003cp\u003e形式上,令 $$$M \u003d 10^9 + 7$$$。可以证明答案可以表示为一个不可约分数 $$$\\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数且 $$$q \\not \\equiv 0 \\pmod{M}$$$。输出等于 $$$p \\cdot q^{-1} \\bmod M$$$ 的整数。换句话说,输出这样一个整数 $$$x$$$,使得 $$$0 \\le x \u0026lt; M$$$ 和 $$$x \\cdot q \\equiv p \\pmod{M}$$$。\u003c/p\u003e"}},{"title":"示例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\n3 3 2\n2 1 10\n6 3 10\n6 4 10\n100 1 1\n4 4 0\n69 4 20\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n5\n375000012\n500000026\n958557139\n0\n49735962\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个测试用例中,整个游戏有 $$$3$$$ 轮,由于 $$$m \u003d 3$$$,Bob 必须在每轮中添加。因此,Alice 应该每轮选择她能选择的最大数字,即 $$$k \u003d 2$$$。\u003c/p\u003e\u003cp\u003e在第三个测试用例中,Alice 有一种策略可以保证得分为 $$$\\frac{75}{8} \\equiv 375000012 \\pmod{10^9 + 7}$$$。\u003c/p\u003e\u003cp\u003e在第四个测试用例中,Alice 有一种策略可以保证得分为 $$$\\frac{45}{2} \\equiv 500000026 \\pmod{10^9 + 7}$$$。\u003c/p\u003e"}}]}