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

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

Idx	Name	Rating
A	Shift Sort	800
B	Another Divisibility Problem	900
C	Ultimate Value	1500
D	A Cruel Segment's Thesis	2000
E1	Prime Gaming (Easy Version)	2200
E2	Prime Gaming (Hard Version)	2500
F	Sum Minimisation	2900

Codeforces Round 1049 (Div. 2)