CF2140E2 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<c\_2<\\ldots<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$$$.

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