D. Получить единицу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Вивека есть изначально пустой массив $$$a$$$ и некоторая целая константа $$$m$$$.

Он выполняет следующий алгоритм:

  1. Выбрать случайное целое число $$$x$$$ равновероятно в диапазоне от $$$1$$$ до $$$m$$$ и добавить в конец $$$a$$$.
  2. Вычислить наибольший общий делитель чисел в массиве $$$a$$$.
  3. Если он равен $$$1$$$, то закончить.
  4. Иначе продолжить с шага $$$1$$$.

Найдите математическое ожидание длины массива $$$a$$$. Можно показать, что его можно представить как $$$\frac{P}{Q}$$$, где $$$P$$$ и $$$Q$$$ взаимнопростые целые числа и $$$Q\neq 0 \pmod{10^9+7}$$$. Выведите значение $$$P \cdot Q^{-1} \pmod{10^9+7}$$$.

Входные данные

Первая и единственная строка содержит целое число $$$m$$$ ($$$1 \leq m \leq 100000$$$).

Выходные данные

Выведите одно целое число — математическое ожидание длины массива $$$a$$$ как $$$P \cdot Q^{-1} \pmod{10^9+7}$$$.

Примеры
Входные данные
1
Выходные данные
1
Входные данные
2
Выходные данные
2
Входные данные
4
Выходные данные
333333338
Примечание

В первом примере Вивек может добавлять только числа в диапазоне от $$$1$$$ до $$$1$$$, так что у него получится массив $$$a=[1]$$$, после чего алгоритм завершится. Так как длина массива $$$a$$$ всегда получится равной $$$1$$$, то математическое ожидание также будет равно $$$1$$$.

Во втором примере Вивек каждый раз будет дописывать в массив или $$$1$$$ или $$$2$$$, так что после выполнения алгоритма он получит список, который состоит из некоторого количества $$$2$$$ (возможно нулевого) и заканчивается одной $$$1$$$. Математическое ожидание длины списка равно $$$1\cdot \frac{1}{2} + 2\cdot \frac{1}{2^2} + 3\cdot \frac{1}{2^3} + \ldots = 2$$$.