配点 : 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