C. Cowardly Lizard IV
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
This is the first problem in the formal contest featuring the "Cowardly Lizard" background.
— susenyang, Legend of Kangaroo Splay

Before General Kangaroo duels with Kangaroo Splay again, he chooses to enhance his combat abilities first. General Kangaroo has a sequence $$$a_1, a_2, \dots, a_n$$$, from which he can gain energy. For a given interval $$$a_l, \dots, a_r (1 \leq l \lt r \leq n)$$$, General Kangaroo can choose an integer $$$k(l \leq k \lt r)$$$ and calculate:

$$$$$$\dfrac{1}{ \sum_{i=l}^{k} a_i } + \dfrac{1}{ \sum_{i=k + 1}^{r} a_i }$$$$$$

Strangely, the smaller this value is, the greater the enhancement of General Kangaroo's combat abilities. General Kangaroo hopes to maximize the enhancement of his combat abilities, which means that for given $$$l$$$ and $$$r$$$, you need to calculate the minimum value of $$$\frac{1}{ \sum_{i=l}^{k} a_i } + \frac{1}{ \sum_{i=k + 1}^{r} a_i }$$$. You need to answer $$$q$$$ queries from General Kangaroo, where in each query he will tell you $$$l$$$ and $$$r$$$, and you need to compute this minimum value.

Formally, given the sequence $$$a_1, a_2, \dots, a_n$$$, you need to answer $$$q$$$ queries, each providing $$$l$$$ and $$$r$$$, and you need to find:

$$$$$$ \min_{k = l}^{r-1} \left\{ \frac{1}{ \sum_{i=l}^{k} a_i } + \frac{1}{ \sum_{i=k + 1}^{r} a_i } \right\}$$$$$$

The answer should be given modulo $$$10^9 + 7$$$.

  • Let $$$m = 10^9 + 7$$$. It can be proven that the answer to this problem can be expressed as a reduced fraction $$$\dfrac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \mod m$$$. You need to find such an integer $$$x(0 \leq x \lt m)$$$, such that $$$x\times q \equiv p \mod m$$$.
Input

The input consists of multiple test cases.

First, a line containing an integer $$$T(1 \leq T \leq 10^4)$$$, indicating the number of test cases.

For each test case, first input a line with two integers $$$n, q(2 \leq n, q \leq 5 \times 10^5)$$$, representing the length of the sequence and the number of queries.

Next, input a line with $$$n$$$ integers $$$a_1, a_2, \dots, a_n(1 \leq a_i \leq 10^3)$$$, representing the sequence obtained by General Kangaroo.

Then, input $$$q$$$ lines, each containing two integers $$$l_i, r_i(1 \leq l_i \lt r_i \leq n)$$$, where $$$l_i$$$ and $$$r_i$$$ represent the $$$i$$$-th query.

It is guaranteed that for all data in a test case, the sum of $$$n$$$ and the sum of $$$q$$$ do not exceed $$$5 \times 10^5$$$.

Output

Output a total of $$$T$$$ lines.

For each test case, output a line with $$$q$$$ integers, representing the answers to the $$$q$$$ queries in order. The answers should be given modulo $$$10^9 + 7$$$.

Example
Input
2
5 3
1 2 3 4 5
1 5
1 4
1 3
3 2
4 6 2
1 3
2 3
Output
277777780 416666670 666666672
375000003 666666672
Note

In the first test case, for the second query, we need to find:

$$$$$$ \min \left\{ \dfrac{1}{ a_1 } + \dfrac{1}{ a_2 + a_3 + a_4 } , \dfrac{1}{ a_1 + a_2 } + \dfrac{1}{a_3 + a_4 }, \dfrac{1}{ a_1 + a_2 + a_3 } + \dfrac{1}{ a_4 } \right\} $$$$$$

Calculating this gives the minimum value as $$$\dfrac{5}{12}$$$, which modulo $$$10^9 + 7$$$ is $$$416666670$$$.