← 返回题目列表

Codeforces · 594/D

D. 请求

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

今天在数学课上,老师告诉 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