C. Sigma Problem (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The only difference is that $$$q=1$$$, $$$l=1$$$ and $$$r=n$$$ in this version.

You are given an array $$$a$$$ of length $$$n$$$. Note $$$$$$s(l,r) = \sum_{i=l}^{r} \sum_{j=i}^{r} \prod_{k=i}^j a_k$$$$$$

where $$$\prod_{k=i}^j a_j$$$ is defined as the product of all elements in the array $$$a$$$ from index $$$i$$$ to $$$j$$$, i.e. $$$(a_i \times a_{i+1} \times ... \times a_j)$$$.

You need to handle $$$q$$$ queries. Each query gives two numbers $$$l$$$, $$$r$$$ $$$(1 \le l \le r \le n)$$$, and you should output $$$s(l,r)$$$.

For each query, you need to output the value modulo $$$10^9+7$$$.

Input

The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 10^5)$$$.

For each test case:

  • The first line contains a single integer $$$n$$$, $$$q$$$ $$$(2 \leq n \leq 10^{6}$$$, $$$q=1)$$$, the length of the array;
  • The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$;
  • For the next $$$q$$$ lines, each line contains two integers $$$l$$$, $$$r$$$ $$$(l=1$$$, $$$r=n)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{6}$$$.

Output

For each query, output ina new line  — the value of $$$s(l,r)$$$ modulo $$$10^9+7$$$.

Example
Input
2
3 1
2 4 3
1 3
4 1
1000000000 1000000000 1000000000 1000000000
1 4
Output
53
1834
Note

In the first test case, $$$a=[2,4,3]$$$ and you need to calculate $$$s(1,3)$$$ in the first query.

For $$$i = 1$$$: $$$$$$ \begin{align*} j = 1: & \quad \prod_{k=1}^{1} a_k = 2 \\ j = 2: & \quad \prod_{k=1}^{2} a_k = 2 \times 4 = 8 \\ j = 3: & \quad \prod_{k=1}^{3} a_k = 2 \times 4 \times 3 = 24 \\ \end{align*} $$$$$$

For $$$i = 2$$$: $$$$$$ \begin{align*} j = 2: & \quad \prod_{k=2}^{2} a_k = 4 \\ j = 3: & \quad \prod_{k=2}^{3} a_k = 4 \times 3 = 12 \\ \end{align*} $$$$$$

For $$$i = 3$$$: $$$$$$ \begin{align*} j = 3: & \quad \prod_{k=3}^{3} a_k = 3 \\ \end{align*} $$$$$$

Thus, $$$s(1,3) = 2+8+34+4+12+3 = 53$$$.