{"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\"\u003eThis is the hard version of the problem. The difference is the constraints on $$$n$$$, $$$m$$$ and $$$t$$$. You can make hacks only if all versions of the problem are solved.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eAlice and Bob are given the numbers $$$n$$$, $$$m$$$ and $$$k$$$, and play a game as follows:\u003c/p\u003e\u003cp\u003eThe game has a score that Alice tries to maximize, and Bob tries to minimize. The score is initially $$$0$$$. The game consists of $$$n$$$ turns. Each turn, Alice picks a \u003cspan class\u003d\"tex-font-style-bf\"\u003ereal\u003c/span\u003e number from $$$0$$$ to $$$k$$$ (inclusive) which Bob either adds to or subtracts from the score of the game. But throughout the game, Bob has to choose to add at least $$$m$$$ out of the $$$n$$$ turns.\u003c/p\u003e\u003cp\u003eBob gets to know which number Alice picked before deciding whether to add or subtract the number from the score, and Alice gets to know whether Bob added or subtracted the number for the previous turn before picking the number for the current turn (except on the first turn since there was no previous turn).\u003c/p\u003e\u003cp\u003eIf Alice and Bob play optimally, what will the final score of the game be?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains a single integer $$$t$$$ ($$$1 \\le t \\le 10^5$$$) — the number of test cases. The description of test cases follows.\u003c/p\u003e\u003cp\u003eEach test case consists of a single line containing the three integers, $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \\le m \\le n \\le 10^6, 0 \\le k \u0026lt; 10^9 + 7$$$) — the number of turns, how many of those turns Bob \u003cspan class\u003d\"tex-font-style-it\"\u003ehas to\u003c/span\u003e add, and the biggest number Alice can choose, respectively.\u003c/p\u003e\u003cp\u003eIt is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case output a single \u003cspan class\u003d\"tex-font-style-bf\"\u003einteger\u003c/span\u003e number — the score of the optimal game modulo $$$10^9 + 7$$$.\u003c/p\u003e\u003cp\u003eFormally, let $$$M \u003d 10^9 + 7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \\not \\equiv 0 \\pmod{M}$$$. Output the integer equal to $$$p \\cdot q^{-1} \\bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \\le x \u0026lt; M$$$ and $$$x \\cdot q \\equiv p \\pmod{M}$$$.\u003c/p\u003e"}},{"title":"Examples","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\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case, the entire game has $$$3$$$ turns, and since $$$m \u003d 3$$$, Bob has to add in each of them. Therefore Alice should pick the biggest number she can, which is $$$k \u003d 2$$$, every turn.\u003c/p\u003e\u003cp\u003eIn the third test case, Alice has a strategy to guarantee a score of $$$\\frac{75}{8} \\equiv 375000012 \\pmod{10^9 + 7}$$$.\u003c/p\u003e\u003cp\u003eIn the fourth test case, Alice has a strategy to guarantee a score of $$$\\frac{45}{2} \\equiv 500000026 \\pmod{10^9 + 7}$$$.\u003c/p\u003e"}}]}