Consider the following function:

\( F(X) \) = Number of divisors of integer X

You are given an array that consists of \(N\) integers. You are also provided \(M\) queries. There can be only one type of query, \(query(l,r)\). You are required to determine the product of all the numbers in the range from \(l\) to \(r\). The output can contain the values of \(l\) and \(r\). Your task is to print the result of function \(F(X)\) mod \(10^9 +7 \) for that product.

Input format

• First line: Two integers \(N\) and \(M\) denoting the number of array elements and the number of queries
• Next line: \(N\) numbers denoting the elements of the array
• Next \(M\) lines: Two integers \(l\) and \(r\) for which the query must be answered

Output format

For each query, you are required to print a single number denoting the answer to that query mod \(10^9 +7\).

Constraints

\( 1\le N \le 5\times10^5 \)

\(1 \le M \le 4\times10^5 \)

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

\( 1 \le a[i] \le 10 \)

Note: Each element of the array cannot contain a value that is greater than \(10\).