第3回 ドワンゴからの挑戦状 本選(オープンコンテスト)

B - ニワンゴくんの約数


Time limit時間制限 : 2.525sec / Memory limitメモリ制限 : 252.525MB

配点 : 1100

問題文

ニワンゴくんは、正の整数からなる数列 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

Submit提出する