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}$