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: VERY_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
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)


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()))
	if m == 1:
		print(binmod(n, k, MVAL))
	else:
		clen = [1] + [0] * k
		hwm = 1
		mhwm = 1
		for ai in ays:
			v = (ai - 1) % m + 1
			for llen in range(v, hwm + 1, m):
				clen[llen] = (clen[llen] + clen[llen - 1]) % MVAL
			if hwm < k and mhwm == v:
				hwm += 1
				mhwm += 1
				if mhwm > m:
					mhwm = 1
		print(clen[k])


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()))


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])


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)


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


def readValues(f):
	s = input()
	return list(map(f, s.split()))
T = int(input())
for k in range(T):
	(n, k, m) = readValues(int)
	a = readValues(int)
	count = [0 for i in range(k + 1)]
	count[0] = 1
	for v in a:
		vmod = v % m
		for i in range(k - (k % m - vmod) % m, 0, -m):
			count[i] = (count[i] + count[i - 1]) % 1000000007
	print(count[k])