Large Sub-Arrays

You are given an array A with size Nand two integers M and K.

Let's define another array B with size NM as the array that's formed by concatenating M copies of array A.

You have to find the number of sub-arrays of the array B with sum K. Since the answer can be very large you have to print the answer mod 10^9+7.

Input Format:

The first line contains an integer T denoting the number of test cases.

The first line of each test case contains 3 space separated integers N and M and K.

Next line contains N space separated integers denoting the array elements.

Output Format:

For each test case, print the required answer in a new line.

Constraints:

1T10

1N,M10⁵

1K10¹⁶

1Ai10⁶

SAMPLE INPUT

2

3 2 2

3 1 5

4 2 5

1 4 2 3

SAMPLE OUTPUT

2

13

Explanation

For the first sample array A is {3,1,5} and m=2.

b={3,1,5,3,1,5}

value of K is 2.

sub-arrays whose sum is l<=K are {1},{1} and hence the answer is 2.