E2. Prime Gaming (Hard Version)
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The difference between the versions is that in this version, $$$m \le 10^6$$$. You can hack only if you solved all versions of this problem.

A valid configuration is defined as an arrangement of $$$n$$$ piles of stones such that:

  • The number of stones in each pile is an integer between $$$1$$$ and $$$m$$$ (both inclusive).

Given a valid configuration of $$$n$$$ piles of stones, some indices from $$$1$$$ to $$$n$$$ are marked as good. Alice and Bob start playing a game taking $$$n-1$$$ turns alternately with Alice going first. In each turn, they have to perform the following operation:

  • Choose any integer $$$i$$$ such that $$$1 \le i \le p$$$ (where $$$p$$$ is the number of piles left) and $$$i$$$ is good, and remove the $$$i$$$-th pile completely.

Note that after performing the operation once, the number of piles decreases by $$$1$$$ and the remaining piles are re-indexed. The game will end when there is only one pile left. It is guaranteed that the index $$$1$$$ is always good.

Let $$$x$$$ denote the number of stones in the final remaining pile. Alice wants to maximize $$$x$$$, whereas Bob wants to minimize it. Both Alice and Bob play optimally.

Find the sum of $$$x$$$ over all the possible valid configurations modulo $$$10 ^ 9 + 7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each testcase contains two integers $$$n$$$ ($$$1 \le n \le 20$$$) and $$$m$$$ ($$$1 \le m \le 10^6$$$) — the number of piles and the upper bound on the number of stones in a pile.

The second line of each testcase contains a single integer $$$k$$$ ($$$1 \le k \le n$$$) — the number of indices marked as good.

The third line of each testcase contains $$$k$$$ integers $$$c_1,c_2,\ldots,c_k$$$ ($$$1=c_1 \lt c_2 \lt \ldots \lt c_k\le n$$$) — the good indices. It is guaranteed that $$$1$$$ is always a good index (i.e. $$$c_1=1$$$).

It is guaranteed that the sum of $$$2^n$$$ over all test cases does not exceed $$$2^{20}$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each testcase, print a single integer — the sum of $$$x$$$ over all the possible valid configurations modulo $$$10 ^ 9 + 7$$$.

Example
Input
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
Output
18
33664
909076242
683044824
901058932
Note

For the first test case, the valid configurations are: $$$[1, 1]$$$, $$$[1,2]$$$, $$$[1, 3]$$$, $$$[2, 1]$$$, $$$[2, 2]$$$, $$$[2,3]$$$, $$$[3,1]$$$, $$$[3,2]$$$, $$$[3,3]$$$.

As there are only $$$2$$$ piles of stones, Alice can only choose the first pile and remove it. Thus, the sum of $$$x$$$ is equal to $$$1+1+1+2+2+2+3+3+3= 18$$$.