SOLVE

LATER

Large Sub-Arrays

/

You are given an array **\(A\)** with size \(N\) and two integers \(M\) and \(K\).

Let's define another array **\(B\)** with size \(N \times 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 \(\leq 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 \leq T \leq 10\)
- \(1 \leq N,M \leq 10^5\)
- \(1 \leq K \leq 10^{16}\)
- \(1 \leq A_i \leq 10^6\)

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.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB