如果 joke 还在，这题应当会出现在他的鲜花里吧。
虽然确实不难，但是我还是不理解 5:00 切的是什么人才。
题目一眼看上去就很生成函数。先不管长度总和，先考虑求方案数。这个限制看起来就很容斥，我们钦定多少对数相等，其它任意填。那么答案的生成函数就是：
\[F(x) = \frac{1}{1 - G(x)}, G(x) = \sum_{i=1}^{\infty} \frac{x^i}{1 + x^i}
\]
上述式子就是将钦定相等的连续段合起来计算，容斥系数为 \((-1)^{j - 1}\)。
考虑长度。求 \(\sum i f_i\) 很自然能想到多项式求导，那么我们引入第二个元 \(y\) 为序列长度，那么上式子改写为：
\[F(x, y) = \frac{1}{1 - G(x, y)}, G(x, y) = \sum_{i=1}^{\infty} \frac{x^iy}{1 + x^iy}
\]
对 \(y\) 求导，可得：
\[\frac{\partial}{\partial y}F(x, y) = \frac{\frac{\partial}{\partial y} (G(x, y) - 1)}{(1-G(x, y))^2}, \frac{\partial}{\partial y} G(x, y) = \sum_{i=1}^{\infty} \frac{x^i}{(1 + x^iy)^2}
\]
我们不关心 \(y\)，所以直接带入 \(y=1\)，那么最后我们要求的答案 \(H(x)\) 就是：
\[H(x) = \frac{\displaystyle \sum_{i=1}^{\infty} \frac{x^{i}}{(1+x^i)^2}}{\left(1-\displaystyle \sum_{i=1}^{\infty} \frac{x^i}{1+x^i}\right)^2}
\]
分子分母都可以暴力拆开计算（调和级数，共 \(O(n \log n)\) 项），于是再加上多项式求逆就做完了。
int main() {
scanf("%d", &n);
f.set(n), g.set(n);
for (int i = 1; i <= n; i++) {
for (int j = 1; i * j <= n; j++) {
f[i * j] = (f[i * j] + ((j & 1) ? 1ll : P - 1ll) * j) % P;
g[i * j] = (g[i * j] + ((j & 1) ? 1ll : P - 1ll)) % P;
}
}
h = f * ((g * (-1) + 1) * (g * (-1) + 1)).inv(n + 1);
printf("%d\n", h[n]);
return 0;
}