#P1139D. Steps to One
-
ID: 4677
Type: RemoteJudge
2000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Steps to One
No submission language available for this problem.
Description
Vivek initially has an empty array $a$ and some integer constant $m$.
He performs the following algorithm:
- Select a random integer $x$ uniformly in range from $1$ to $m$ and append it to the end of $a$.
- Compute the greatest common divisor of integers in $a$.
- In case it equals to $1$, break
- 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}$.
The first and only line contains a single integer $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}$.
Input
The first and only line contains a single integer $m$ ($1 \leq m \leq 100000$).
Output
Print a single integer — the expected length of the array $a$ written as $P \cdot Q^{-1} \pmod{10^9+7}$.
Samples
1
1
2
2
4
333333338
Note
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$.