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$