
132  The 14th Zhejiang University Programming Contest  F
You are given a list of numbers A_{1} A_{2} .. A_{N} and M queries. For the ith query:
You task is to calculate F_{i}(R_{i}) for each query. Because the answer can be very large, you should output the remainder of the answer divided by 1000000007. InputThere are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case: The first line contains two integers N, M (1 <= N, M <= 100000). The second line contains N integers A_{1} A_{2} .. A_{N} (1 <= A_{i} <= 1000000000). The next M lines, each line is a query with two integer parameters L_{i}, R_{i} (1 <= L_{i} <= R_{i} <= N). OutputFor each test case, output the remainder of the answer divided by 1000000007. Sample Input1 4 7 1 2 3 4 1 1 1 2 1 3 1 4 2 4 3 4 4 4 Sample Output1 2 5 13 11 4 4 