Preface
不会dp，所以反演（感谢@judgelight）。
Solution
考虑期望式子：
\[\begin{aligned}
E(len)&=\sum_iP(len=i)\times i\\
&=\sum_iP(len=i)\sum_{j=1}^i1\\
&=\sum_i\sum_{j=1}^iP(len=i)\\
&=\sum_j\sum_{i\ge j}P(len=i)\\
&=\sum_jP(len\ge j)\\
&=1+\sum_jP(len>j)\\
&=1+\sum_j1-P(len\le j)\\
\end{aligned}
\]
设 \(f_{i,j}\) 表示 \(len=i,gcd=j\) 的方案数，\(F_{i,j}\) 表示 \(len=i, j|gcd\) 的方案数。
则：
\[\begin{aligned}
F_{i,j}&=\sum_{j|d}f_{i,d}=\lfloor\frac{m}{j}\rfloor^i\\
f_{i,j}&=\sum_{j|d}\mu(\frac{d}{j})F_{i,d}\\
f_{i,j}&=\sum_{j|d}\mu(\frac{d}{j})\lfloor\frac{m}{d}\rfloor^i\\
\end{aligned}
\]
题目要求 \(gcd=1\)，所以我们只关注 \(f_{i,1}\)，则：
\[f_{i,1}=\sum_{d=1}^m\mu(d)\lfloor\frac{m}{d}\rfloor^i
\]
根据定义，\(P(len\le j)=\frac{f_{j,1}}{m^j}\)，为什么上面那一坨不是 \(\sum_{k=1}^{j} f_{k,1}\) 呢，因为如果长度在小于 \(j\) 时 \(gcd\) 已经等于 \(1\) 了的话，无论怎样添加数，\(gcd\) 都恒为 \(1\)。
让我们再看回期望式子：
\[\begin{aligned}
E(len)&=1+\sum_j1-P(len\le j)\\
&=1+\sum_j1-\frac{f_{j,1}}{m^j}\\
&=1+\sum_j1-\frac{\sum_{d=1}^m\mu(d)\lfloor\frac{m}{d}\rfloor^j}{m^{j-1}}\\
&=1+\sum_j\frac{m^{j}-\sum_{d=1}^m\mu(d)\lfloor\frac{m}{d}\rfloor^{j}}{m^j}\\
&=1-\sum_j\sum_{d=2}^m\mu(d)\frac{\lfloor\frac{m}{d}\rfloor^j}{m^{j}}\\
&=1-\sum_{d=2}^m\mu(d)\sum_{j}\left(\frac{\lfloor\frac{m}{d}\rfloor}{m}\right)^j\\
\end{aligned}
\]
现在 \(j\) 还无法处理，那我们处理一下。
发现：
令 \(S=x^1+x^2+x^3+\dots\)
∴\(xS=x^2+x^3+x^4+\dots\)
∴\((x-1)S=-x\)
即\(S=\frac{x}{1-x}\)
知道了这个，\(j\) 自然就解决了：
\[\begin{aligned}
E(len)&=1-\sum_{d=2}^m\mu(d)\sum_{j}\left(\frac{\lfloor\frac{m}{d}\rfloor}{m}\right)^j\\
&=1-\sum_{d=2}^m\mu(d)\frac{\frac{\lfloor\frac{m}{d}\rfloor}{m}}{1-\frac{\lfloor\frac{m}{d}\rfloor}{m}}\\
&=1-\sum_{d=2}^m\mu(d)\frac{\lfloor\frac{m}{d}\rfloor}{m-\lfloor\frac{m}{d}\rfloor}\\
\end{aligned}
\]
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7;
int m;
int primes[N], idx, miu[N], tmp;
bool st[N];
int ksm(int a, int b, int p) {
int res = 1;
while(b) {
if(b & 1) res = (1ll * res * a) % p;
a = (1ll * a * a) % p;
b >>= 1;
}
return res;
}
#define inv(x) ksm(x, mod - 2, mod)
void euler(int N){
miu[1] = 1; N ++ ;
for (int i = 2; i < N; ++ i ) {
if(!st[i]) primes[ ++ idx] = i, miu[i] = -1;
for (int j = 1, p = primes[1]; j <= idx && p * i < N; ++ j , p = primes[j]) {
st[p * i] = 1;
if(i % p == 0) {miu[p * i] = 0; break;}
miu[p * i] = -miu[i];
}
}
}
int main(){
cin >> m;
euler(m);
for (int d = 2; d <= m; ++ d )
tmp = ((tmp + 1ll * miu[d] * (m / d) * inv(m - m / d)) % mod + mod) % mod;
cout << ((1 - tmp) % mod + mod) % mod;
return 0;
}