After the death of their mother, Alphonse and Edward now live with Pinako and Winry.

Pinako is worried about their obsession with Alchemy, and that they don't give attention to their studies.
So to improve their mathematical solving ability, every day she gives a mathematical problem to solve. They can go out to practice Alchemy only after they have solved the problem.
Help them by solving the given problem, so that they can go early today for their Alchemy practice.
Given an array A$A$ of N$N$ non-negative integers and two integers K$K$ and M$M$. Find the number of subsequences of array A$A$ of length K$K$ which satisfies the following property:

Suppose the subsequence is S=S1S2…SK$S = S_1S_2 \ldots S_K$, then for all i$i$ such that 1≤i≤K$1 \leq i \leq K$,
Si%M=i%M S_i \% M = i \% M
should hold true, where Si$S_i$ denotes the i$i$-th element of the subsequence, using 1-based indexing.
As the number of subsequences may be very large, output the answer modulo 1000000007$1000000007$.
PS: We also proposed the idea of making a look-alike clone through alchemy and keeping it in front of the study table. But it seems impossible to convince Edward to make a clone of his exact same height, and not taller than him. So solving the problem for him was a better choice.

-----Input:-----
- The first line contains T$T$, the number of test cases. Then the test cases follow.
- For every test case, the first line contains N$N$, K$K$ and M$M$.
- For every test case, the second line contains N$N$ integers Ai$A_{i}$ ( 1≤i≤N$1 \leq i \leq N$).

-----Output:-----
For every test case, output in a single line an integer denoting the number of valid subsequences modulo 109+7$10^9+7$

-----Constraints-----
- 1≤T≤100$1 \leq T \leq 100$
- 1≤N≤104$1 \leq N \leq 10^{4}$
- 1≤K≤N$1 \leq K \leq N$
- ⌈K100⌉≤M≤100×K$\lceil \frac{K}{100}\rceil \leq M \leq 100\times K$
- 0≤Ai≤109$0 \leq A_{i} \leq 10^{9}$

-----Sample Input:-----
1
12 4 3
4 5 6 7 1 4 6 9 0 0 10 2

-----Sample Output:-----
8

-----Explanation:-----
The subsequences of length 4$4$, satisfying the given criteria are [4,5,6,7]$[4, 5, 6, 7]$, [4,5,6,10]$[4, 5, 6, 10]$, [4,5,6,10]$[4, 5, 6, 10]$, [4,5,6,1]$[4, 5, 6, 1]$, [4,5,9,10]$[4, 5, 9, 10]$ ,[4,5,6,4]$[4, 5, 6, 4]$ , [4,5,0,10]$[4, 5, 0, 10]$ and [4,5,0,10]$[4, 5, 0, 10]$. This accounts for a total of 8$8$ valid subsequences.
Let us take one subsequence and see why it satisfies the given property. Consider [4,5,9,10]$[4, 5, 9, 10]$.
- S1%M=4%3=1=1%3=1%M$S_1 \% M = 4 \% 3 = 1 = 1 \% 3 = 1 \% M$
- S2%M=5%3=2=2%3=2%M$S_2 \% M = 5 \% 3 = 2 = 2 \% 3 = 2 \% M$
- S3%M=9%3=0=3%3=3%M$S_3 \% M = 9 \% 3 = 0 = 3 \% 3 = 3 \% M$
- S4%M=10%3=1=4%3=4%M$S_4 \% M = 10 \% 3 = 1 = 4 \% 3 = 4 \% M$
All the valid i$i$ satisfy the condition, and hence this is a valid subsequence.

见题面

见题面