Statement : E2. Prime Gaming (Hard Version)

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$.

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$.

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

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$.