Xiao Hai interesuje się wojskowością, dlatego dzisiaj postanowiła zagrać w grę militarną.
W grze żołnierze Xiao Hai mają $n$ punktów stacjonowania, ponumerowanych od $1$ do $n$. Aby rozwijać gospodarkę, Xiao Hai zbudowała wiele dróg między punktami. Dokładniej, dla każdego punktu $i$ o numerze innym niż $1$, Xiao Hai zbudowała dwukierunkową drogę o długości $1$ łączącą $i$ oraz $\frac{i}{h(i)}$, gdzie $h(i)$ jest zdefiniowane jako najmniejszy dzielnik pierwszy liczby $i$. (Łatwo dowieść, że wszystkie punkty utworzą drzewo).
W celu zapewnienia bezpieczeństwa kraju, Xiao Hai postanowiła, że każdego dnia żołnierze będą patrolować wszystkie pary punktów. Oczywiście patrolowanie wiąże się z pewnymi kosztami; koszt patrolowania między punktem $i$ a punktem $j$ jest równy najkrótszej odległości między tymi punktami.
Xiao Hai chce wiedzieć, jaki jest całkowity koszt patrolowania każdego dnia. Ponieważ wynik może być bardzo duży, należy wypisać go modulo $10^9+7$.
Dokładniej, Xiao Hai chce obliczyć: $$ \sum_{i=1}^{n-1}\sum_{j=i+1}^ndis(i,j)\pmod{ 10^9+7} $$ gdzie $dis(i,j)$ oznacza najkrótszą odległość między $i$ oraz $j$ w tym drzewie.
Wejście
Jedna linia zawierająca liczbę całkowitą $n$, oznaczającą liczbę punktów stacjonowania.
Wyjście
Jedna linia zawierająca liczbę całkowitą, oznaczającą sumę najkrótszych odległości między wszystkimi parami punktów w drzewie.
Przykład
Wejście 1
6
Wyjście 1
31
Wejście 2
50
Wyjście 2
4986
Ograniczenia
Dla $100\%$ danych: $n\le 10^{10}$
| Numer podzadania | $n \le $ | Punkty |
|---|---|---|
| 1 | $10^5$ | 10 |
| 2 | $5 \cdot 10^7$ | 35 |
| 3 | $10^9$ | 25 |
| 4 | $10^{10}$ | 30 |