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$