Bash got tired on his journey to become the greatest Pokemon master. So he decides to take a break and play with functions.
Bash defines a function f 0(n), which denotes the number of ways of factoring n into two factors p and q such that gcd(p, q) = 1. In other words, f 0(n) is the number of ordered pairs of positive integers (p, q) such that p·q = n and gcd(p, q) = 1.
But Bash felt that it was too easy to calculate this function. So he defined a series of functions, where f r + 1 is defined as:
Where (u, v) is any ordered pair of positive integers, they need not to be co-prime.
Now Bash wants to know the value of f r(n) for different r and n. Since the value could be huge, he would like to know the value modulo 109 + 7. Help him!
Input
The first line contains an integer q (1 ≤ q ≤ 106) — the number of values Bash wants to know.
Each of the next q lines contain two integers r and n (0 ≤ r ≤ 106, 1 ≤ n ≤ 106), which denote Bash wants to know the value f r(n).
Output
Print q integers. For each pair of r and n given, print f r(n) modulo 109 + 7 on a separate line.
Example
input
5
0 30
1 25
3 65
2 5
4 48
output
8
5
25
4
630
Solution:
#include <bits/stdc++.h> using namespace std; const int md = 1000000007; inline void add(int &a, int b) { a += b; if (a >= md) { a -= md; } } inline int mul(int a, int b) { return (long long) a * b % md; } const int N = 1010101; const int ALPHA = 21; int f[N][ALPHA]; int p[N]; int a[N]; int dp[777][777]; int main() { for (int j = 0; j < ALPHA; j++) { f[0][j] = (j == 0); } for (int i = 1; i < N; i++) { int sum = 0; for (int j = 0; j < ALPHA; j++) { add(sum, f[i - 1][j]); f[i][j] = sum; } } for (int i = 1; i < N; i++) { p[i] = i; } for (int i = 2; i < N; i++) { if (p[i] == i) { for (int j = i + i; j < N; j += i) { if (p[j] == j) { p[j] = i; } } } } int tt; scanf("%d", &tt); while (tt--) { int r, n; scanf("%d %d", &r, &n); int cnt = 0; int tmp = n; while (tmp > 1) { int d = p[tmp]; a[cnt] = 0; while (tmp % d == 0) { a[cnt]++; tmp /= d; } cnt++; } for (int i = 0; i <= cnt; i++) { for (int j = 0; j <= i; j++) { dp[i][j] = 0; } } dp[0][0] = 1; for (int i = 0; i < cnt; i++) { for (int j = 0; j <= i; j++) { add(dp[i + 1][j], mul(dp[i][j], f[r][a[i]])); add(dp[i + 1][j + 1], mul(dp[i][j], f[r + 1][a[i] - 1])); } } int ans = 0; for (int j = cnt; j >= 0; j--) { add(ans, ans); add(ans, dp[cnt][j]); } printf("%d\n", ans); } return 0; }