Large Sub-Arrays
/

## Arrays, Data Structures, One-dimensional, oct circuits

Problem
Editorial
Analytics

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$
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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...