C. Christ of Discord
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have proven that you are a sigma, but you still do not have your sigma badge. You decide to climb the steps of the Christ of Discord. At the top, the supreme sigma shows you a list $$$a$$$, composed of $$$n$$$ numbers. He tells you that if you answer his $$$q$$$ questions correctly, you will earn the sigma badge. Each question provides you with two numbers $$$l$$$ and $$$r$$$, which represent a range of the list of numbers. You have to respond with the sigma function of the product of the numbers that appear in the range.

The sigma function is defined as the sum of all divisors of a number including the number itself:

For example, $$$\sigma(6) = 12$$$ because the divisors of $$$6$$$ are: $$$1, 2, 3, 6$$$.

The list of numbers $$$a$$$ is represented as $$$a_1, a_2, a_3, \ldots, a_n$$$ and the range consists of $$$a_l, a_{l+1}, \ldots, a_r$$$. The answer to a question is $$$\sigma(a_l*a_{l+1}*\ldots*a_r)$$$, which is the sigma function applied to the product of the numbers in the range.

Now, to obtain your sigma badge and be recognized internationally, you must answer the $$$q$$$ questions correctly.

Input

The input consists of two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^4$$$), followed by $$$n$$$ integers, the list $$$a$$$ ($$$1 \leq a_i \leq 10^5$$$). Then, there are $$$q$$$ lines representing the questions, each with two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$).

Output

You must print $$$q$$$ numbers, the answer to each question. Since the number can be very large, respond with each of the results modulo $$$10^9 + 7$$$.

Example
Input
10 5
1 2 3 4 5 6 7 8 9 10
1 1
10 10
1 10
1 3
7 10
Output
1
18
15334088
12
19344