CF1139D Steps to One

Vivek 最初有一个空数组 $a$ 和一个整数常数 $m$。 他执行如下算法： 1. 从 $1$ 到 $m$ 的范围内等概率随机选择一个整数 $x$，并将其添加到 $a$ 的末尾。 2. 计算数组 $a$ 中所有整数的最大公约数。 3. 如果最大公约数等于 $1$，则停止操作。 4. 否则，返回第 1 步。 求数组 $a$ 的期望长度。可以证明，这个期望值可以表示为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 是互质的整数，且 $Q\neq 0 \pmod{10^9+7}$。请输出 $P \cdot Q^{-1} \pmod{10^9+7}$。

第一行包含一个整数 $m$（$1 \leq m \leq 100000$）。

输出一个整数，表示数组 $a$ 的期望长度，形式为 $P \cdot Q^{-1} \pmod{10^9+7}$。

在第一个样例中，Vivek 只能从 $1$ 到 $1$ 选择整数，因此第一次添加后 $a=[1]$，算法立即结束。数组长度始终为 $1$，所以期望值也是 $1$。 在第二个样例中，Vivek 每次会添加 $1$ 或 $2$，最终数组中会有若干个 $2$（可能为零），最后有一个 $1$。期望长度为 $1\cdot \frac{1}{2} + 2\cdot \frac{1}{2^2} + 3\cdot \frac{1}{2^3} + \ldots = 2$。 由 ChatGPT 4.1 翻译