Migrated from Lutece 2670 艾莉斯之章 - 牢狱的医生

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

那里是井底

什么都看不到

什么都听不见

什么都想不出

有如铅块般沉重的黑暗，从内心中涌出，充满体内——

就是那样的感觉。

我曾经憧憬着光芒。

将我的一切都涂满的，强烈的光芒。

---

艾莉斯是牢狱最有名的医生，甚至说的上是牢狱内唯一一名医生。而她本身对钱的需求并不大，每个人只收取一小部分治疗费，因此深受牢狱人民的关注与憧憬。

一天，艾莉斯突然找到缇娅，想让她教自己做菜。

缇娅非常开心，并告诉艾莉斯做菜的一个小技巧，能够极大帮助做出来的菜肴更加美味。

艾莉斯想要做的菜一共有 $m$ 种原料，她给每种原料标上 $1\sim m$ 的记号（每个数字恰好出现一次）。设 $S$ 为当前锅中的原料标号的可重集合，一开始锅里什么也没有（即 $S$ 为空集）。她需要执行以下步骤：

1. 从 $[1,m]$ 中等概率地选择一个整数 $x$；
2. 将 $x$ 加入到 $S$ 中；
3. 计算 $S$ 中所有标号的 $\gcd$，设为 $g$；
4. 若 $g=1$，则这道菜就做好了；否则，回到第 $1$ 步。

这道菜的美味度就是 $S$ 中的元素个数。由于缇娅不是很聪明，每次做菜都是凭感觉做，艾莉斯想知道这样做之后这道菜的美味度的期望值是多少。由于答案可以表示成 $P/Q$ 的形式，输出 $P \cdot Q^{-1} \bmod (10^9 + 7)$。

Input

输入仅一行一个正整数 $m$。

Output

输出一行表示答案。

Samples

2

2

4

333333338

Constraints

$1\le m \le 10^{9}$

Resources

2021 UESTC ICPC Training for Math and Geometry