#P1139D. Steps to One

Steps to One

Description

Vivek initially has an empty array aa and some integer constant mm.

He performs the following algorithm:

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

Find the expected length of aa. It can be shown that it can be represented as PQ\frac{P}{Q} where PP and QQ are coprime integers and Q0(mod109+7)Q\neq 0 \pmod{10^9+7}. Print the value of PQ1(mod109+7)P \cdot Q^{-1} \pmod{10^9+7}.

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

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

Input

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

Output

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

Samples

样例输入 1

1

样例输出 1

1

样例输入 2

2

样例输出 2

2

样例输入 3

4

样例输出 3

333333338

Note

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

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