小海对军事很感兴趣，所以今天她找了一款军事游戏来玩。
游戏中，小海的士兵有 $n$ 个驻点，标号为 $1, \dots, n$。为了发展经济，小海在驻点之间建了很多通路，具体来说，对于任意一个标号不为 $1$ 的驻点 $i$，小海修建了一条连接 $i$ 和 $\frac{i}{h(i)}$ 且距离为 $1$ 的双向道路，其中 $h(i)$ 定义为 $i$ 的最小质因子。（不难证明，所有驻点会形成一棵树）。
为了保护国家的安全，小海决定每一天让士兵在所有点对间巡逻。当然，巡逻也需要一定的开销，具体来说，在驻点 $i$ 和驻点 $j$ 间巡逻的开销为两点间的最短距离。
此时小海想知道每一天巡逻的开销是多少，由于答案太大，你只需要输出答案对 $10^9+7$ 取模的结果即可。
具体来说，小海想要知道 $$ \sum_{i=1}^{n-1}\sum_{j=i+1}^ndis(i,j)\pmod{ 10^9+7} $$ 其中 $dis(i,j)$ 表示的是 $i$ 和 $j$ 在这棵树上的最短距离。
入力
一行，一个整数 $n$，表示驻点数量。
出力
一行，一个整数，表示树的所有点对最短距离和。
入出力例
入力 1
6
出力 1
31
入力 2
50
出力 2
4986
制約
对于 $100\%$ 的数据：$n \le 10^{10}$
| 子任务编号 | $n \le $ | 分值 |
|---|---|---|
| 1 | $10^5$ | 10 |
| 2 | $5 \cdot 10^7$ | 35 |
| 3 | $10^9$ | 25 |
| 4 | $10^{10}$ | 30 |