Consider the Function:

$F(X)$ = Number of Divisors of Integer X

You have been given an array consisting of N integers and M queries .There can be only 1 type of query i.e :

$query(l,r)$ : You need to find product of all number in the range from l to r inclusive and then output the result of function $F(X)$ mod $10^9 +7$ for that product.

Input Format:

The first line contains 2 integers N and M denoting the number of array elements and the number of queries The next line contains N numbers denoting the elements of the array .

Each of the next M lines contains 2 integers l and r for whom the query needs to be answered.

Output Format:

For each query you need to print a single number denoting the answer to that query mod $10^9 +7$

Constraints:

$1\le N \le 5*10^5$

$1 \le M \le 4*10^5$

$1 \le l \le r \le N$

$1 \le a[i] \le 10$

Note: Each element of the array shall not have a value greater than 10.