今天在数学课上,老师告诉 Vovochka,正整数 φ(n) 的欧拉函数是一个算术函数,用于计算小于或等于 n 且与 n 互质的正整数。数字 1 与所有正整数互质,并且 φ(1) = 1。
现在老师给了 Vovochka 一个由 n 个正整数 a1, a2, ..., an 组成的数组,以及一个处理 q 个查询 li ri 的任务 — 计算并打印 $$\varphi \left( \prod_{i=l}^{r} a_i \right)$$ modulo 109 + 7。由于这对二年级学生来说太难了,所以你决定帮助 Vovochka。
输入
输入的第一行包含数字 n (1 ≤ n ≤ 200 000) — 给予 Vovochka 的数组长度。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 106)。
第三行包含整数 q (1 ≤ q ≤ 200 000) — 查询数。接下来的 q 行包含查询,每行一个。每个查询由段 li 和 ri (1 ≤ li ≤ ri ≤ n) 的边界定义。
输出
打印 q 个数字 — 每个查询的欧拉函数值,以 109 + 7 为模计算。
示例
输入 #1
10 1 2 3 4 5 6 7 8 9 10 7 1 1 3 8 5 6 4 8 8 10 7 9 7 10
输出 #1
1 4608 8 1536 192 144 1152
输入 #2
7 24 63 13 52 6 10 1 6 3 5 4 7 1 7 2 4 3 6 2 6
输出 #2
1248 768 12939264 11232 9984 539136
注意
在第二个示例中,值的计算方式如下:
- φ(13·52·6) = φ(4056) = 1248
- φ(52·6·10·1) = φ(3120) = 768
- φ(24·63·13·52·6·10·1) = φ(61326720) = 12939264
- φ(63·13·52) = φ(42588) = 11232
- φ(13·52·6·10) = φ(40560) = 9984
- φ(63·13·52·6·10) = φ(2555280) = 539136