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\).