A continued fraction is an expression of the form $${\displaystyle a_1+\frac{1}{a_2+\frac{1}{\ddots +\frac{1}{a_n}}}}$$ where $a_1,a_2,\dots ,a_n$ are positive integers.

Bob has managed to obtain an array $A$ of $N$ positive integers. He now wants to compute $Q$ continued fractions, the $i$-th of which uses the elements from indices $l_i$ to $r_i$ (inclusive) in the array, in order. For example, if $A=[1,4,5,2]$, $l_i=2$, and $r_i=4$, the answer would be: $${\displaystyle 4+\frac{1}{5+\frac{1}{2}}=4+\frac{2}{11}=\frac{46}{11}}$$ Please help Bob with this task!

Constraints

$1\le N,Q\le 300000$
$1\le A_i\le {10}^9$
$1\le l_i\le r_i\le N$

Subtask 1 [10%]

$1\le N,Q\le 1000$

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input will contain two space-separated integers, $N$ and $Q$.
The second line will contain $N$ space-separated integers, $A_1$ through $A_N$.
The next $Q$ lines will each contain two space-separated integers, $l_i$ and $r_i$.

Output Specification

$Q$ lines, each containing two space-separated integers: the numerator and denominator of the $i$-th continued fraction, in lowest terms. Since these numbers may be very large, you may output them mod ${10}^9+7$. However, note that the fraction must be in lowest terms before modding; reducing the fraction after modding may not yield the same result!

Sample Input

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

Sample Output

46 11
5 4
5 1