CF757E Bash Plays with Functions

题目描述

Bash 在成为最伟大的宝可梦大师的旅途中感到有些疲惫，于是他决定休息一下，玩玩函数。

Bash 定义了一个函数 $f_0(n)$，表示将 $n$ 分解为 $p$ 和 $q$ 两个因数，并且满足 $\gcd(p, q) = 1$ 的分解方法数。换句话说，$f_0(n)$ 是满足 $p \cdot q = n$ 且 $\gcd(p, q) = 1$ 的有序正整数对 $(p, q)$ 的数量。

但 Bash 觉得这个函数太简单了，于是他又定义了一系列函数，$f_{r+1}$ 的定义如下：

其中 $(u, v)$ 是任意的有序正整数对，不要求互质。

现在 Bash 想要知道不同 $r$ 和 $n$ 下 $f_r(n)$ 的值。由于答案可能很大，他想要结果对 $10^9 + 7$ 取模。请你帮帮他！

输入格式

第一行包含一个整数 $q$（$1 \leq q \leq 10^6$），表示 Bash 想要查询的次数。

接下来的 $q$ 行，每行包含两个整数 $r$ 和 $n$（$0 \leq r \leq 10^6$，$1 \leq n \leq 10^6$），表示 Bash 想要知道 $f_r(n)$ 的值。

输出格式

输出 $q$ 个整数，每行一个答案，分别对应每个 $(r, n)$ 下 $f_r(n)$ 对 $10^9+7$ 取模后的结果。

输入输出样例 #1

输入 #1

5
0 30
1 25
3 65
2 5
4 48

输出 #1

8
5
25
4
630

说明/提示

由 ChatGPT 5 翻译