You are given an array A with size N and two integers M and K.
Let's define another array B with size N×M 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:
- 1≤T≤10
- 1≤N,M≤105
- 1≤K≤1016
- 1≤Ai≤106
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.
