## 【Codeforces 757E】Bash Plays with Functions

### 解题报告

Ⅰ. 设$x$的素因子种类数为$g(x)$那么$f_0(x)$等于$2^{g(x)}$
Ⅱ. 由规律Ⅰ可得，$f_0(x)$为积性函数，又$f_i(x)=f_{i-1} * 1(x)$，于是我们可用归纳证明得$f_i(x)$均为积性函数
Ⅲ. 设$p$为素数，$f_r(p^k)$与$p$无关，且满足递推式：$f_r(p^k)=\sum\limits_{i=0}^{k}{f_{r-1}(p^i)}$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000009;
const int MOD = 1000000007;

int tot,vis[N],pri[N],sur[N],g[N][21];

inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void prework() {
for (int i=2;i<N;i++) {
if (!vis[i]) pri[++tot] = i, sur[i] = i;
for (int j=1;j<=tot&&i*pri[j]<N;j++) {
vis[i*pri[j]] = 1; sur[i*pri[j]] = pri[j];
if (i % pri[j] == 0) break;
}
}
g[0][0] = 1;
for (int i=1;i<=20;i++) g[0][i] = 2;
for (int i=1;i<N;i++) {
for (int j=0;j<=20;j++) {
g[i][j] = ((j? g[i][j-1]: 0) + g[i-1][j]) % MOD;
}
}
}

inline int solve(int a, int b) {
int ret = 1;
for (int cnt=0,p=sur[b];b>1;cnt=0,p=sur[b]) {
while (b % p == 0) b /= p, cnt++;
ret = (LL)ret * g[a][cnt] % MOD;
}
return ret;
}

int main() {
prework();
for (int T=read(),a,b;T;T--) {
a = read(); b = read();
printf("%d\n",solve(a,b));
}
return 0;
}