CF1628D2 Game on Sum (Hard Version)

这是该问题的困难版本。不同之处在于 $n$、$m$ 和 $t$ 的约束条件。只有在所有版本的问题都被解决后，你才能进行 hack。 Alice 和 Bob 得到三个数 $n$、$m$ 和 $k$，并按照如下规则进行游戏： 游戏有一个分数，Alice 试图最大化分数，Bob 试图最小化分数。初始分数为 $0$。游戏共进行 $n$ 回合。每一回合，Alice 从 $0$ 到 $k$（包含 $0$ 和 $k$）中选择一个实数，Bob 可以选择将这个数加到分数上，或者从分数中减去。但在整个游戏过程中，Bob 必须在 $n$ 回合中至少有 $m$ 回合选择加法。 在每一回合，Bob 会在知道 Alice 选择了哪个数之后，决定是加还是减；而 Alice 在选择当前回合的数之前，会知道上一回合 Bob 是加还是减（第一回合除外，因为没有上一回合）。 如果 Alice 和 Bob 都采取最优策略，游戏的最终分数是多少？

输入的第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。接下来的每个测试用例包含一行，包含三个整数 $n$、$m$ 和 $k$（$1 \le m \le n \le 10^6, 0 \le k < 10^9 + 7$），分别表示回合数、Bob 必须加法的最少回合数，以及 Alice 能选择的最大数。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出一个整数，表示最优游戏的分数对 $10^9 + 7$ 取模后的结果。 形式化地，设 $M = 10^9 + 7$。可以证明答案可以表示为不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{M}$。输出等于 $p \cdot q^{-1} \bmod M$ 的整数。换句话说，输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

在第一个测试用例中，整个游戏有 $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}$。 由 ChatGPT 4.1 翻译