← 返回题目列表

Codeforces · 757/E

E. Bash 与函数一起玩

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

巴什在成为最伟大的神奇宝贝大师的旅程中感到疲倦。所以他决定休息一下,玩玩函数。

Bash 定义了一个函数 f0(n),它表示将 n 分解为两个因子 p 和 q 使得 gcd(p, q) = 1 的方式数。换句话说,f0(n) 是使得 p·q = n 且 gcd(p, q) = 1 的正整数 (p, q) 有序对的数量。

但 Bash 觉得计算这个函数太容易了。于是他定义了一系列函数,其中fr+1定义为:

$$f_{r+1}(n) = \sum_{u\cdot v=n} \frac{f_r(u) + f_r(v)}{2},$$

其中 (u, v) 是任意有序的正整数对,它们不必是互质的。

现在 Bash 想知道不同 r 和 n 的 fr(n) 值。由于该值可能很大,他想知道模 109 + 7 的值。帮助他!

输入

第一行包含一个整数 q (1 ≤ q ≤ 106) — Bash 想知道的值的数量。

接下来的 q 行包含两个整数 r 和 n (0 ≤ r ≤ 106, 1 ≤ n ≤ 106),这表示 Bash 想知道值 fr(n)。

输出

打印 q 个整数。对于给定的每一对 r 和 n,在单独的行上打印 fr(n) 模 109 + 7。

示例

输入 #1

5
0 30
1 25
3 65
2 5
4 48

输出 #1

8
5
25
4
630