← 返回题目列表

Codeforces · 2140/E2

E2. Prime Gaming (硬版)

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

这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$m \le 10^6$$$。只有解决了该问题的所有版本,您才能破解。

A 有效 配置被定义为$$$n$$$堆石头的排列,使得:

  • 每堆石子的数量是 $$$1$$$ 和 $$$m$$$ 之间的整数(包含两者)。

给定 有效 $$$n$$$ 堆石头的配置, 从 $$$1$$$ 到 $$$n$$$ 的一些索引被标记为良好。 Alice 和 Bob 开始玩 $$$n-1$$$ 轮流的游戏,Alice 先玩。在每一轮中,他们必须执行以下操作:

  • 选择任意整数 $$$i$$$,使得 $$$1 \le i \le p$$$ (其中 $$$p$$$ 是剩下的堆数)并且 $$$i$$$ 是 好,并完全删除第 $$$i$$$ 堆。

注意,执行一次操作后,堆的数量减少了$$$1$$$,并且剩余的堆被重新索引。当只剩下一堆时游戏结束。保证索引 $$$1$$$ 总是好的。

让 $$$x$$$ 表示最后剩下的一堆石头的数量。 Alice 想要最大化 $$$x$$$,而 Bob 想要最小化它。 Alice 和 Bob 都发挥最佳。

求所有可能的 $$$x$$$ 的总和 有效 配置以 $$$10 ^ 9 + 7$$$ 为模。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ ($$$1 \le n \le 20$$$) 和 $$$m$$$ ($$$1 \le m \le 10^6$$$) - 堆的数量和堆中石子数量的上限。

每个测试用例的第二行包含一个整数 $$$k$$$ ($$$1 \le k \le n$$$) — 标记为良好的索引数量。

每个测试用例的第三行包含 $$$k$$$ 整数 $$$c_1,c_2,\ldots,c_k$$$ ($$$1=c_1 \lt c_2 \lt \ldots \lt c_k\le n$$$) - 好的索引。 保证 $$$1$$$ 始终是一个好的索引(即 $$$c_1=1$$$).

保证所有测试用例的$$$2^n$$$总和不超过$$$2^{20}$$$。

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

输出

对于每个测试用例,打印一个整数 - 所有可能的 $$$x$$$ 的总和 有效 配置以 $$$10 ^ 9 + 7$$$ 为模。

示例

输入
复制

5
2 3
1
1
7 4
3
1 4 6
12 31
6
1 3 5 7 9 11
11 121
11
1 2 3 4 5 6 7 8 9 10 11
19 6969
2
1 19

输出
复制

18
33664
909076242
683044824
901058932

注意

对于第一个测试用例, 有效 配置为:$$$[1, 1]$$$、$$$[1,2]$$$、$$$[1, 3]$$$、$$$[2, 1]$$$、$$$[2, 2]$$$、$$$[2,3]$$$、$$$[3,1]$$$、$$$[3,2]$$$、 $$$[3,3]$$$。

由于只有 $$$2$$$ 堆石头,爱丽丝只能选择第一堆并将其移走。因此,$$$x$$$ 之和等于 $$$1+1+1+2+2+2+3+3+3= 18$$$。