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.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
mod = 10**9 + 7
for i in range(int(input())):
    n,k,m = tuple(map(int, input().split()))
    a = list(map(int, input().split()))
    ans = [0 for i in range(k+1)]
    ans[0] = 1
    curr_ending = 1
    for i in range(n):
     mod_a = a[i]%m
     start = curr_ending - (curr_ending%m - mod_a)%m
     if(mod_a == curr_ending%m and curr_ending<k):
      curr_ending += 1
     for i in range(start, 0, -m):
      ans[i] += ans[i-1]
      if(ans[i] > mod):
       ans[i] = ans[i] - mod
    print(ans[k])

# cook your dish here
mod = 10**9 + 7
for i in range(int(input())):
    n,k,m = tuple(map(int, input().split()))
    a = list(map(int, input().split()))
    ans = [0 for i in range(k+1)]
    ans[0] = 1
    curr_ending = 1
    for i in range(n):
     mod_a = a[i]%m
     start = curr_ending - (curr_ending%m - mod_a)%m
     if(mod_a == curr_ending%m and curr_ending<k):
      curr_ending += 1
     for i in range(start, 0, -m):
      ans[i] += ans[i-1]
      if(ans[i] > mod):
       ans[i] = ans[i] - mod
    print(ans[k])

# cook your dish here
mod = 10**9 + 7
for i in range(int(input())):
    n,k,m = tuple(map(int, input().split()))
    a = list(map(int, input().split()))
    ans = [0 for i in range(k+1)]
    ans[0] = 1
    curr_ending = 1
    for i in range(n):
     mod_a = a[i]%m
     start = curr_ending - (curr_ending%m - mod_a)%m
     if(mod_a == curr_ending%m and curr_ending<k):
      curr_ending += 1
     for i in range(start, 0, -m):
      ans[i] += ans[i-1]
      if(ans[i] > mod):
       ans[i] = ans[i] - mod
    print(ans[k])

  


# cook your dish here
M = 10**9+7
for _ in range(int(input())):
    n,k,m=(int(s) for s in input().split())
    l = [int(s)%m for s in input().split()]
    ans = [0]*(k+1)
    i = 1
    for j in range(n):
     mov = 0
     just = 0
     if (i%m+1)%m==l[j] and i<k:
      if ans[i]!=0:
       just=1
      mov = 1
     w = i - (i%m-l[j])%m
     while w>=1:
      if w==1:
       ans[w]+=1
      else:
       ans[w]+=ans[w-1]
      w-=m
     if mov:
      i+=1
      if just:
       ans[i] = ans[i-1]
    print(ans[k]%M) 

M = 10**9+7
for _ in range(int(input())):
    n,k,m=(int(s) for s in input().split())
    l = [int(s)%m for s in input().split()]
    ans = [0]*(k+1)
    i = 1
    for j in range(n):
     mov = 0
     just = 0
     if (i%m+1)%m==l[j] and i<k:
      if ans[i]!=0:
       just=1
      mov = 1
     w = i - (i%m-l[j])%m
     while w>=1:
      if w==1:
       ans[w]+=1
      else:
       ans[w]+=ans[w-1]
      w-=m
     if mov:
      i+=1
      if just:
       ans[i] = ans[i-1]
    print(ans[k]%M) 

# cook your dish here
t = int(input())
MOD = 10**9+7
for _ in range(t) :
    n,k,m= list(map(int,input().split()))
    b = [0 for i in range(k)]
    a = list(map(int,input().split()))
    if(m == 1) :
     for i in range(n) :
      for j in range(k-1,-1,-1) :
       if(j == 0) :
        b[j] = (b[j]+1)%MOD
       else :
        b[j] = (b[j-1] + b[j])%MOD
    else :
     for val in a:
      mod = val % m
      if(mod == 0) :
       mod = m
      for j in range(mod-1,k,m) :
       if(j == 0) :
        b[j] = (b[j]+1)%MOD
       else :
        b[j] = (b[j-1] + b[j])%MOD
    print(b[-1]%MOD)

mod=10**9+7
for _ in range(int(input())):
    n,k,m=list(map(int,input().split()))
    a=list([(int(x)-1)%m+1 for x in input().split()])
    arr=[0]*k
    arr.insert(0,1)
    for i in range(n):
     end=a[i]+m*((k-a[i])//m)
     for j in range(end,a[i]-1,-m):
      arr[j]=(arr[j]+arr[j-1])%mod
    print(arr[-1])
 


def modinv(v,m):
    v %= m
    pv = m
    pc = 0
    c = 1
    while v > 0:
     q, a = divmod(pv, v)
     pc, c = c, pc-q*c
     pv, v = v, a
    return pc % m

def binmod(n,r,m):
    if 2*r > n: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    tp = 1
    bm = 1
    for t in range(1, r+1):
     bm = bm*t%m
     tp = tp*(n+1-t)%m
    return (tp*modinv(bm,m))%m

MVAL = 1000000007
for ti in range(int(input())):
    n,k,m = map(int,input().split())
    ays = list(map(int,input().split()))

# https://www.codechef.com/problems/GRUMPMA
from sys import stdin

def modinv(v,m):
    v %= m
    pv = m
    pc = 0
    c = 1
    while v > 0:
     q, a = divmod(pv, v)
     pc, c = c, pc-q*c
     pv, v = v, a
    return pc % m

def binmod(n,r,m):
    if 2*r > n: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    tp = 1
    bm = 1
    for t in range(1, r+1):
     bm = bm*t%m
     tp = tp*(n+1-t)%m
    return (tp*modinv(bm,m))%m

MVAL = 1000000007

# https://www.codechef.com/problems/GRUMPMA
from sys import stdin

def modinv(v,m):
    v %= m
    pv = m
    pc = 0
    c = 1
    while v > 0:
     q, a = divmod(pv, v)
     pc, c = c, pc-q*c
     pv, v = v, a
    return pc % m

def binmod(n,r,m):
    if 2*r > n: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    tp = 1
    bm = 1
    for t in range(1, r+1):
     bm = bm*t%m
     tp = tp*(n+1-t)%m
    return (tp*modinv(bm,m))%m

MVAL = 1000000007