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<c_2<\ldots<c_k\le n)) — the good indices. It is guaranteed that (1) is always a good index (i.e. $$