You are given \(N\) integers \(A_1,A_2, ... ,A_N\) and \(Q\) queries. In each query, you are given two integers \(L\) and \(R\) (\(1 ≤ L ≤ R ≤ N\)).

For each query, write a program to find the value of the following expression:

\( GCD( F(A_L), F(A_{L+1}), F(A_{L+2}) ...... F(A_R) ) \% 10^9+7\)

Input format

• First line: Two space-separated integers \(N\) and \(Q\)
• Second line: \(N\) space-separated integers denoting the elements of array \(A\)
• Next \(Q\) lines: Two space-separated integers \(L\) and \(R\)

Output format

For each query, print the value of the expression.

Note

• The Fibonacci series is defined as:

  \( F(N) \) = \( F (N-1) + F(N-2) \) \(\forall \space N \ge 3 \)
  \( F(1) =1\) , \(F(2) = 1 \)

• The GCD of two numbers is the greatest common divisor of those numbers. For example, \(GCD(2, 4)\ =\ 2\).

Constraints

\(1 \le N \le 10^5\)
\(1 \le Q \le 10^5\)
\(1 \le A_i \le 10^9\)
\(1 \le L \le R \le N\)