CF1139D.Steps to One

Vivek initially has an empty array $a$ and some integer constant $m$.

He performs the following algorithm:

1. Select a random integer $x$ uniformly in range from $1$ to $m$ and append it to the end of $a$.
2. Compute the greatest common divisor of integers in $a$.
3. In case it equals to $1$, break
4. Otherwise, return to step $1$.

Find the expected length of $a$. It can be shown that it can be represented as $\frac{P}{Q}$ where $P$ and $Q$ are coprime integers and $Q\neq 0 \pmod{10^9+7}$. Print the value of $P \cdot Q^{-1} \pmod{10^9+7}$.

维韦克初始时有一个空数组 $a$ 和某个整数常数 $m$。

他执行如下算法：

1. 在区间 $[1, m]$ 内均匀随机选取一个整数 $x$，并将其追加到数组 $a$ 的末尾；
2. 计算数组 $a$ 中所有整数的最大公约数（GCD）；
3. 若该最大公约数等于 $1$，则终止算法；
4. 否则，返回步骤 1。

求数组 $a$ 的期望长度。可以证明该期望值可表示为 $\frac{P}{Q}$，其中 $P$ 与 $Q$ 互质，且 $Q \not\equiv 0 \pmod{10^9+7}$。请输出 $P \cdot Q^{-1} \pmod{10^9+7}$ 的值。

The first and only line contains a single integer $m$ ($1 \leq m \leq 100000$).

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

Print a single integer — the expected length of the array $a$ written as $P \cdot Q^{-1} \pmod{10^9+7}$.

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

In the first example, since Vivek can choose only integers from $1$ to $1$, he will have $a=[1]$ after the first append operation, and after that quit the algorithm. Hence the length of $a$ is always $1$, so its expected value is $1$ as well.

In the second example, Vivek each time will append either $1$ or $2$, so after finishing the algorithm he will end up having some number of $2$'s (possibly zero), and a single $1$ in the end. The expected length of the list is $1\cdot \frac{1}{2} + 2\cdot \frac{1}{2^2} + 3\cdot \frac{1}{2^3} + \ldots = 2$.

在第一个例子中，由于Vivek只能选择从 $1$ 到 $1$ 的整数，因此他在第一次追加操作后将得到 $a=[1]$，随后便退出算法。因此，$a$ 的长度恒为 $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$。