SOLVE
LATER
You are given an array \(A\) of size \(N\). You have also defined an array \(B\) as the concatenation of array \(A\) for infinite number of times.
For example, if \(A=\{A_1, A_2, A_3\}\), then \(B= \{A_1, A_2, A_3, A_1, A_2, A_3,.....\}\).
Now, you are given \(Q\) queries. Each query consists of two integers, \(L_i\) and \(R_i\). Your task is to calculate the sum of the subarray of \(N\) from index \(L_i\) to \(R_i\).
Note: As the value of this output is very large, print the answer as modulus \(10^9+7\).
Input format
Output format
For each test case, print \(Q\) space-separated integers that denote the answers of the provided \(Q\) queries. Print the answer to each test case in a new line.
Constraints
\(1\le T\le100\\ 1\le N\le 10^4\\ 1\le Q\le 10^4\\ 1\le A_i\le 10^9\\ 1\le L_i\le R_i\le 10^{18}\\\)
\(A=\{4,1,5\}\\ B=\{4,1,5,4,1,5,4,1,5,4,1,5,...\} \)
Query #1:
L=1, R=4, elements are {4,1,5,4}. Sum=4+1+5+4=14.
Query #2:
L=3, R=7, elements are {5,4,1,5,4}. Sum=5+4+1+5+4=19.
Query #3:
L=9, R=10, elements are {5,4}. Sum=5+4=9.