\[f[1] = 0
\]
\]
\[f[i] = 1 + \frac{1}{m} \sum_{j = 1} ^ n f[gcd(i, j)] \ \ \ \ \ \ (i != 1)
\]
\]
- 然后发现后面这一块gcd的个数只可能是i的约数， 那么考虑枚举约数
\[f[i] = 1 + \frac{1}{m}\sum_{d | i} f[d] cnt(d, i)
\]
\]
- \(cnt(d, i)\)表示和[1,m]内与i的gcd为d的数字个数
- 考虑这个东西能够怎么算， \(cnt(d, i)\)显然 等于 \(1\ \ to \ \ (m / d)\) 中 和（i / d)互质的数的个数， 后者是莫比乌斯反演的经典形式
- 然后暴力就能过了
/*
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define ll long long
#define M 100010
#define mmp make_pair
using namespace std;
const int mod = 1000000007;
void add(int &x, int y)
{
x += y;
x -= x >= mod ? mod : 0;
x += x < 0 ? mod : 0;
}
int mul(int a, int b)
{
return 1ll * a * b % mod;
}
int poww(int a, int b)
{
int ans = 1, tmp = a;
for(; b; b >>= 1, tmp = mul(tmp, tmp)) if(b & 1) ans = mul(ans, tmp);
return ans;
}
vector<int> to[M];
int f[M], mu[M], n, ans;
int read()
{
int nm = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
return nm * f;
}
int main()
{
n = read();
mu[1] = 1;
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j += i)
{
to[j].push_back(i);
if(j != i) mu[j] -= mu[i];
}
}
for(int i = 1; i <= n; i++)
{
int p = n / i;
f[i] = mul(f[i] + p, poww(n - p, mod - 2));
add(ans, f[i] + 1);
for(int j = i + i; j <= n; j += i)
{
int d = j / i, s = 0;
for(int k = 0; k < to[d].size(); k++)
{
int v = to[d][k];
add(s, mul(mu[v], p / v));
}
add(f[j], mul(s, f[i] + 1));
}
}
ans = mul(ans, poww(n, mod - 2));
cout << ans << "\n";
return 0;
}