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 300\,000~
~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