CF1628D2.Game on Sum (Hard Version)

This 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.

Alice and Bob are given the numbers $n$, $m$ and $k$, and play a game as follows:

The 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 real 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.

Bob 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).

If Alice and Bob play optimally, what will the final score of the game be?

这是该问题的困难版本。区别在于对 $n$、$m$ 和 $t$ 的约束条件。仅当该问题的所有版本均被解决时，才允许进行 Hack。

Alice 和 Bob 获得三个数 $n$、$m$ 和 $k$，并按如下规则进行一场游戏：

游戏中有一个得分，Alice 试图使该得分最大化，而 Bob 试图使其最小化。游戏初始得分为 $0$。游戏共进行 $n$ 轮。在每一轮中，Alice 从区间 $[0, k]$ 中选择一个实数，Bob 则决定将该数加到当前得分上，或从当前得分中减去该数。但在整场游戏中，Bob 必须在全部 $n$ 轮中至少选择 相加 $m$ 次。

Bob 在决定对该轮 Alice 所选数字执行“加”还是“减”操作之前，能够得知 Alice 当前所选的具体数值；而 Alice 在为当前轮次选择数字之前，能够得知 Bob 在上一轮中对该轮数字执行的是“加”还是“减”操作（第一轮除外，因为不存在上一轮）。

若 Alice 和 Bob 均采取最优策略，游戏最终的得分是多少？

The 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.

Each 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 \lt 10^9 + 7$) — the number of turns, how many of those turns Bob has to add, and the biggest number Alice can choose, respectively.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例由一行组成，包含三个整数 $n$、$m$ 和 $k$（$1 \le m \le n \le 10^6$，$0 \le k \lt 10^9 + 7$），分别表示总轮数、Bob 需要执行加法操作的轮数，以及 Alice 可选择的最大数字。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

For each test case output a single integer number — the score of the optimal game modulo $10^9 + 7$.

Formally, let $M = 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 \lt M$ and $x \cdot q \equiv p \pmod{M}$.

对于每个测试用例，输出一个整数——最优游戏得分对 $10^9 + 7$ 取模的结果。

形式化地，令 $M = 10^9 + 7$。可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，输出满足 $0 \le x \lt M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

In the first test case, the entire game has $3$ turns, and since $m = 3$, Bob has to add in each of them. Therefore Alice should pick the biggest number she can, which is $k = 2$, every turn.

In the third test case, Alice has a strategy to guarantee a score of $\frac{75}{8} \equiv 375000012 \pmod{10^9 + 7}$.

In the fourth test case, Alice has a strategy to guarantee a score of $\frac{45}{2} \equiv 500000026 \pmod{10^9 + 7}$.

在第一个测试用例中，整个游戏共进行 $3$ 轮，且由于 $m = 3$，Bob 必须在每一轮中都执行添加操作。因此 Alice 应在每一轮中都选择她所能选择的最大数字 $k = 2$。

在第三个测试用例中，Alice 存在一种策略，可保证获得分数 $\frac{75}{8} \equiv 375000012 \pmod{10^9 + 7}$。

在第四个测试用例中，Alice 存在一种策略，可保证获得分数 $\frac{45}{2} \equiv 500000026 \pmod{10^9 + 7}$。