← 返回题目列表

Codeforces · 1628/D2

D2. Sum 游戏(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。区别在于 $$$n$$$、$$$m$$$ 和 $$$t$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

Alice 和 Bob 被赋予数字 $$$n$$$、$$$m$$$ 和 $$$k$$$,并玩如下游戏:

游戏有一个分数,Alice 试图最大化,而 Bob 试图最小化。分数最初为 $$$0$$$。游戏由 $$$n$$$ 回合组成。每回合,Alice 从 $$$0$$$ 到 $$$k$$$(含)中选择一个实数,Bob 可以将其添加到游戏分数中或从游戏分数中减去。但在整个游戏中,鲍勃必须选择在 $$$n$$$ 回合中添加至少 $$$m$$$。

鲍勃在决定是否从分数中添加或减去数字之前知道爱丽丝选择了哪个数字,而爱丽丝在选择当前回合的数字之前知道鲍勃是否添加或减去了上一回合的数字(第一回合除外,因为没有上一回合)。

如果 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}$$$。

示例

输入 #1

7
3 3 2
2 1 10
6 3 10
6 4 10
100 1 1
4 4 0
69 4 20

输出 #1

6
5
375000012
500000026
958557139
0
49735962

注意

在第一个测试用例中,整个游戏有 $$$3$$$ 回合,并且由于 $$$m = 3$$$,Bob 必须添加每个回合。因此,爱丽丝应该选择她能选择的最大数字,即每轮 $$$k = 2$$$。

在第三个测试用例中,Alice 有一个策略来保证得分 $$$\frac{75}{8} \equiv 375000012 \pmod{10^9 + 7}$$$。

在第四个测试用例中,Alice 有一个策略来保证得分 $$$\frac{45}{2} \equiv 500000026 \pmod{10^9 + 7}$$$。