美丽的樱花~

求不定方程：
$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$

的正整数解 (x,y) 的数目。

Input
一个整数 n。

Output
一个整数，表示有多少对 (x,y) 满足题意。答案对 10⁹+7 取模。

Example

样例输入
2
样例输出
3
样例说明
共有三个数对 (x,y) 满足条件，分别是 (3,6),(4,4) 和 (6,3)。

Hint
对于 30% 的数据，$n\le 100$；
对于全部数据，$1\le n\le 10^6$。

历程：这道问题我一开始看着求方案数以为又是dp呢，想了一想发现dp 是不行，状态之间的联系基本上上是无，那就先想别的题？于是我又屁颠屁颠的去做别的题。

这道题出的还可以，主要是有个转化的过程，需要一定的数学基础，（数学加油！）

$\frac{x+y}{x\ast y}=\frac{1}{n!}$

进而转化成 $x\ast y-n!(x+y)=0$ 下面的重点要来了，将等式两边同时加上$n{!}^2$ 再进行因式分解

变成 $(x-n!)(y-n!)=n{!}^2$，然后将$n{!}^2$质因式分解，再运用算数基本定理，进而解决问题

代码：

#include <iostream>
#include <cstring>using namespace std;typedef long long LL;const int N = 1e6 + 10, mod = 1e9 + 7;int prime[N], idx, cnt[N];bool vis[N];void get(int x)
{for (int i = 2; i <= x; i ++){if (!vis[i]) prime[idx ++] = i;for (int j = 0; prime[j] <= x / i; j ++){vis[i * prime[j]] = true;if (i % prime[j] == 0) break;}}
}int gett(int a, int b)
{int res = 0;while (a){res += a / b;a  /= b;}return res;    
}int main()
{int n, res = 1;  cin >> n;get(n);for (int i = 0; i < idx; i ++){cnt[i] = gett(n, prime[i]);res = (LL)res * (2 * cnt[i] + 1) % mod;}cout << res << endl;return 0;
}