問題文

ニワンゴくんは、正の整数からなる数列 x_1,\ x_2,\ ...,\ x_N を持っています。次の Q 個のクエリに順に答えてください。

• クエリ: 1 ≦ l_i ≦ r_i ≦ N が与えられるので、x_{l_i},\ x_{l_i+1},\ ...,\ x_{r_i} の積 x_{l_i}x_{l_i+1}...x_{r_i} の約数の個数を 10^9 + 7 で割ったあまりを求めよ。

制約

• 1 ≦ N, Q ≦ 10^5
• 1 ≦ x_i ≦ 10^5 (1 ≦ i ≦ N)
• 1 ≦ l_i ≦ r_i ≦ N (1 ≦ i ≦ Q)
• 入力はすべて整数である。

入力例 1

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

出力例 1

90
24
12
75
6

最初のクエリにおいて、x_1x_2x_3x_4x_5x_6=64800 の約数の個数は 90 個なので、90 を出力します。

入力例 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

出力例 2

1005480
2106
7056
9576
3528
7680