Who does not like a short and precise problem statement? Atleast everyone in CSEmpur does.
You are given an array A consisting of positive integers. The pera of a subarray is defined as the sum of the elements of the subarray. You have to process Q queries. In each query you will be given two integers L and R. You have to print the sum of the pera of all possible subarrays of A in the interval [L, R].
Print the answer modulo 109+7.
Subarray of an array is defined as a continuous sub segment of that array.
Input
The first line of input contains an integer T (1 ≤ T ≤ 105) — the number of test cases.
First line of each test contains two integers n (1 ≤ n ≤ 5×106) and Q(1 ≤ Q ≤ 2×106) — the size of array A and the number of queries.
The next line has n integers A1, A2, ...., An (1 ≤ Ai ≤ 105).
The next Q lines have 2 integers L and R (1 ≤ L ≤ R ≤ n).
It is guaranteed that the sum of n over all test cases does not exceed 5×106 and sum of Q over all test cases does not exceed 2×106.
Output
For each query print the answer in a separate line.
Sample
| Input | Output |
|---|---|
3 3 2 6 9 6 3 3 2 3 6 3 6 2 7 2 8 6 2 6 4 6 5 5 1 1 3 1 1 | 6 30 178 56 8 3 |
Explanation: For the 2nd query of the 2nd test case the subarray is 2, 8, 6. Sum of pera of all possible subarray for this is
(2) + (8) + (6) + (2+8) + (8+6) + (2+8+6) = 56
Dataset is huge. Use fast input and output.
