小海对军事很感兴趣，所以今天她找了一款军事游戏来玩。
游戏中，小海的士兵有 $n$ 个驻点，标号为 $1, ..., 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$，表示驻点数量。
输出
一行，一个整数，表示树的所有点对最短距离和。
样例一
input
6
output
31
样例二
input
50
output
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 |
时间限制：3s
空间限制：512MB