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$$$.