A12566 | 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}$ .

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}$ .