Сяо Хай очень интересуется военным делом, поэтому сегодня она решила поиграть в военную игру.

В игре у солдат Сяо Хай есть $n$ опорных пунктов, пронумерованных от $1$ до $n$. Для развития экономики Сяо Хай построила множество путей между пунктами. А именно, для любого пункта $i$ с номером, отличным от $1$, Сяо Хай построила двустороннюю дорогу длиной $1$ между $i$ и $\frac{i}{h(i)}$, где $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}$