問題文

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

入力

入力は以下の形式で標準入力から与えられる。

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

出力

クエリ毎に、整数 $x_{l_i}x_{l_i+1}...x_{r_i}$ の約数の個数を $10^9 + 7$ で割ったあまりを一行に出力せよ。

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