小海对军事很感兴趣，所以今天她找了一款军事游戏来玩。

游戏中，小海的士兵有 $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}$

时间限制：3s

空间限制：512MB