CF2140E2.Prime Gaming (Hard Version)

这是该问题的困难版本。不同之处在于本版本中 $m \le 10^6$。仅当你解决了所有版本的问题之后，才可以尝试 hack。

一个合法的石堆配置被定义为：有 $n$ 堆石子，每堆中石子的数量是 $1$ 到 $m$ 之间的整数（包含 $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 试图最小化 $x$。两人都会采取最优策略。

请计算所有可能合法石堆配置对应的 $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 < c_2 < \ldots < c_k \le n$）——“好”的下标。保证 $1$ 始终是“好”的（即 $c_1=1$）。

保证所有测试数据中 $\sum 2^n \le 2^{20}$。

保证所有测试数据中 $m$ 的总和不超过 $10^6$。

对每组测试数据，输出一个整数，表示所有可能合法石堆配置中 $x$ 的和，结果对 $10^9+7$ 取模。

对于第一个测试用例，合法的石堆配置有：$[1,1]$、$[1,2]$、$[1,3]$、$[2,1]$、$[2,2]$、$[2,3]$、$[3,1]$、$[3,2]$、$[3,3]$。

由于只有 $2$ 堆石子，Alice 只能选择第一堆并移除，所以 $x$ 的和为 $1+1+1+2+2+2+3+3+3=18$。

由 ChatGPT 5 翻译