← 返回题目列表

AtCoder · dwango2017final_b

B. 二王后君的除数

中文机器翻译题面 查看原题

配点 : 1100 点

問題文

Niwango-kun 是一个正整数序列。 我有 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