Prefix Sum Queries

You are given an array of n integers and q queries. The array is 1-indexed. For each query, you are given two integers l and r, and you need to compute the sum of the subarray from index l to r inclusive. Since the sum can be very large, output it modulo \(10^9+7\).

Details

• The first line of input contains two integers \(n\) and \(q\).
• The second line contains \(n\) space-separated integers representing the array elements.
• Each of the next \(q\) lines contains two integers \(l\) and \(r\), representing a query.

For each query, compute

[ \text{result} = \left( \sum_{i=l}^{r} A_i \right) \mod 10^9+7 ]

and print the result on a new line for each query.

inputFormat

The input is given via standard input (stdin) and has the following format:

n q
A1 A2 A3 ... An
l1 r1
l2 r2
... 
lq rq

Here, \(n\) is the number of elements in the array, and \(q\) is the number of queries. \(A_i\) denotes the \(i\)-th element of the array. Each query consists of two space-separated integers \(l\) and \(r\), the start and end indices of the subarray (1-indexed).

outputFormat

For each query, print a single integer representing the sum of the specified subarray modulo \(10^9+7\> on a new line. The output should be written to standard output (stdout).

## sample

5 3
1 2 3 4 5
1 3
2 4
1 5

6
9
15

</p>