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$.