All Tracks Data Structures Arrays 1-D Problem

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?