問題文

ニワンゴくんは、正の整数からなる数列 $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)$
• 入力はすべて整数である。

入力例 1Copy

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

出力例 1Copy

90
24
12
75
6

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

入力例 2Copy

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

出力例 2Copy

1005480
2106
7056
9576
3528
7680