It's an extremely cold day in BitLand and Vasya is in the mood to do some complex arithmetic. So, he defines the following 2 functions:

\(F(x)\) : Largest divisor of number x that is \(< x\).

\(Q(A,l,r)\): Product of \(F(x)\) where \(l \le x \le r\) in a certain array A

Now, Vasya has been given an array A of size N. He needs to answer certain types of queries based on this array. In each query. he shall be given 2 integers l and r and he needs to find \(Q(A,l,r)\) He find this task too easy and has passed it on to you. Can you do it. As the answer to each query can be relatively large, find it Modulo \(10^9+7\)

Input Format :

The first line contains a single integers N denoting the size of array A. The next line contains N space separated integers denoting the elements of array A. The next line contains a single integer T denoting the number of queries. Each of the next T lines contain 2 integers l and r.

Output Format:

Print the answer to each query on a new line. As the answer may be large, print it Modulo \(10^9+7\)

Constraints:

\( 1 \le N \le 10^6 \)

\( 2 \le A[i] \le 10^7 \)

\( 1 \le T \le 10^5 \)

\( 1 \le l \le r \le N \)