问题描述

尼瓦尔宫君有一个由正整数组成的数列$x_1,\\ x_2,\\ ...,\\ x_N$。请按顺序回答以下 $Q$ 个查询。

• 查询：给定 $1 \leq l_i \leq r_i \leq 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 \leq N, Q \leq 10^5$
• $1 \leq x_i \leq 10^5 (1 \leq i \leq N)$
• $1 \leq l_i \leq r_i \leq N (1 \leq i \leq 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

对于第一个查询，$x_1x_2x_3x_4x_5x_6x_7x_8x_9x_{10}=1551957747200008576$，其约数个数为1005480，因此输出1005480。