小海對軍事很感興趣，所以今天她找了一款軍事遊戲來玩。
遊戲中，小海的士兵有 $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 |