本题为困难版本，与简单版本的区别是：困难版本中 $m\le 10^6$。 只有当你通过本题所有版本时，才可以进行 Hack。

定义合法局面：共 $n$ 堆石子，满足： 每堆石子数量为 $1$ 到 $m$ 之间的整数（包含两端）。

给定一组由 $n$ 堆石子构成的合法局面，将下标 $1$ 到 $n$ 中若干个标记为好下标。

Alice 和 Bob 进行博弈游戏： 共进行 $n-1$ 轮操作，两人轮流行动，Alice 先手。 每一轮必须执行如下操作：

设当前剩余 $p$ 堆石子，选出满足 $1\le i\le p$ 且为好下标的位置 $i$，将第 $i$ 堆石子整堆移除。

注意：每移除一堆后，堆总数减 $1$，剩余石子堆会重新从 $1$ 开始顺序编号。 游戏进行到仅剩最后一堆时结束。 题目保证：下标 $1$ 一定是好下标。

设最后剩余一堆的石子数量为 $x$：

• Alice 目标：最大化 $x$
• Bob 目标：最小化 $x$ 两人均采取最优策略。

求所有合法局面对应的最终 $x$ 之和，答案对 $10^9+7$ 取模。

输入格式

多组测试用例。 第一行一个整数 $t$（$1\le t\le 10^4$），表示测试组数。

每组测试用例：

1. 第一行两个整数 $n,m$（$1\le n\le 20,\ 1\le m\le 10^6$），分别代表石子堆数、每堆石子数的上界。
2. 第二行一个整数 $k$（$1\le k\le n$），表示好下标的数量。
3. 第三行 $k$ 个整数 $c_1,c_2,\dots,c_k$，满足 $1=c_1<c_2<\dots<c_k\le n$，为所有好下标。 题目保证 $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$ 堆石子，Alice 只能选择移除第 $1$ 堆，最终剩余第二堆。 总和：