小海は軍事に興味があり、今日は軍事ゲームをプレイすることにしました。
ゲーム内では、小海の兵士には $1, \dots, n$ と番号付けられた $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
制約
すべてのデータにおいて：$n \le 10^{10}$
| サブタスク番号 | $n \le $ | 配点 |
|---|---|---|
| 1 | $10^5$ | 10 |
| 2 | $5 \cdot 10^7$ | 35 |
| 3 | $10^9$ | 25 |
| 4 | $10^{10}$ | 30 |