题目内容

Vivek 最初有一个空数组 $a$ 和一个整数常数 $m$。他执行以下算法：

1. 在 $1$ 到 $m$ 范围内均匀随机选择一个整数 $x$，并将其追加到数组 $a$ 的末尾。
2. 计算数组 $a$ 中所有整数的最大公约数（GCD）。
3. 如果该 GCD 等于 $1$，则停止；否则返回步骤 1。

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

输入

仅一行包含一个整数 $m$（$1 \le m \le 10^5$）。

输出

输出一个整数——期望长度模 $10^9+7$ 的值。

样例1

1

1

样例2

2

2

样例3

4

333333338

注意

第一个样例：Vivek 只能选择 $1$，因此数组为 $[1]$ 后立即停止，长度恒为 $1$，期望为 $1$。

第二个样例：每次选择 $1$ 或 $2$，最终数组由若干 $2$（可能为零个）和一个结尾的 $1$ 组成。期望长度为 $1 \cdot \frac12 + 2 \cdot \frac{1}{2^2} + 3 \cdot \frac{1}{2^3} + \dots = 2$。