All Tracks Data Structures Arrays 1-D Problem

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