350. Concerned Guardian

0

Medium

Alphonse and Edward live with Pinako and Winry after their mother's passing. Pinako is concerned about their focus on alchemy and lack of attention to their studies.

To improve their math skills, Pinako gives them a daily problem to solve. They can only practice alchemy after solving the problem. Help them solve the given problem so they can start their alchemy practice early today.

Given an array A of N non-negative integers and two integers K and M, find the number of subsequences of array A with length K that satisfy the following property: for all i such that 1≤i≤K, Si%M=i%M, where Si is the i-th element of the subsequence (using 1-based indexing).

As the number of subsequences may be very large, output the answer modulo 1000000007.

Note: We considered creating a clone through alchemy to sit at the study table, but convincing Edward to make a clone of the same height proved impossible. Solving the problem is a better option.

Input Format

The first line contains T, the number of test cases. Then the test cases follow. For each test case, the first line contains N, K, and M. For each test case, the second line contains N integers Ai (1≤i≤N).

Output Format

For each test case, output an integer on a single line representing the number of valid subsequences modulo 109+7.

Example

Input

1 8 4 3 4 5 6 7 9 1 0 10

Output

6

Constraints

1≤T≤100
1≤N≤104
1≤K≤N
ceil(K/100) ≤ M ≤ 100×K
0≤Ai≤109