Reyaan has given you the following problem to solve:

You are given an integer K in base B, represented by an array A of length N such that
0 ≤ A_{i} < B for every 1 ≤ i ≤ N
$\sum_{i=1}^N A_{i} \cdot B^{N-i} = K$

Note that N ≤ B in this problem.

Find the smallest non-negative integer X such that X+K contains every digit from 0 to B-1 in its base-B representation.

X can be very large, so print the answer modulo 10^{9} + 7.

Note: Leading zeros are not counted as part of the number, so for example 12 = 012 has only two distinct digits: 1 and 2. However, 102 does have three distinct digits.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains two space-separated integers N and B — the size of the array A and the base.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$.

------ Output Format ------

For each test case, output on a new line the value of X, modulo 10^{9} + 7.

------ Constraints ------

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{6}$
$2 ≤ B ≤ 10^{6}$
$N ≤ B$
$0 ≤ A_{i} < B$
$A_{1} > 0$, i.e, the given number doesn't contain leading zeros.
- The sum of $B$ across all test cases won't exceed $10^{6}$.

----- Sample Input 1 ------
4
4 4
3 1 0 2
4 5
1 2 3 4
2 2
1 1
1 3
2

----- Sample Output 1 ------
0
500
1
9

----- explanation 1 ------
Test case $1$: All the digits from $0$ to $B-1=3$ are already present in the given array, so $X = 0$.

Test case $2$: In base $5$, $[1, 2, 3, 4]$ represents the integer $194$. The smallest number larger than the given one that contains every digit is $[1, 0, 2, 3, 4]$, which represents
$694$. The difference between them is $500$.

Test case $3$: We have $K = 3$, which is $[1, 1]$ in binary. If we add $X = 1$ to it, we obtain $K+X = 4$, which is $[1, 0, 0]$ in binary and has both digits.

见题面

见题面