Problem Description

Niwango-kun has a sequence of positive integers $x_1,\ x_2,\ ...,\ x_N$. Answer the following $ Q $ queries in order:

• Query: Given $1\ ≦\ l_i\ ≦\ r_i\ ≦\ N$, find the number of divisors of the product $ x_{l_i}x_{l_i+1}...x_{r_i} $ modulo $10^9\ +\ 7$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ x_1 $ $ : $ $ x_N $ $ l_1 $ $ r_1 $ $ : $ $ l_Q $ $ r_Q $

Output Format

For each query, output the number of divisors of the integer $ x_{l_i}x_{l_i+1}...x_{r_i} $ modulo $10^9\ +\ 7$ on a single line.

Sample Input and Output

Sample Input #1

6 5
2
6
5
18
4
15
1 6
2 4
1 3
2 6
4 4

Sample Output #1

90
24
12
75
6

Sample Input #2

10 6
3003
57600
4320
100000
3456
2197
2187
65536
90090
8128
1 10
2 5
3 7
1 4
3 6
7 10

Sample Output #2

1005480
2106
7056
9576
3528
7680

Notes/Hints

Constraints

• $1\ ≦\ N,\ Q\ ≦\ 10^5$
• $1\ ≦\ x_i\ ≦\ 10^5\ (1\ ≦\ i\ ≦\ N)$
• $1\ ≦\ l_i\ ≦\ r_i\ ≦\ N\ (1\ ≦\ i\ ≦\ Q)$
• All inputs are integers.

Sample Explanation 1

In the first query, the number of divisors of $ x_1x_2x_3x_4x_5x_6=64800 $ is $ 90 $, so output $ 90 $.

见题面 Input 部分

见题面 Output 部分