У Вивека есть изначально пустой массив \(a\) и некоторая целая константа \(m\).
Он выполняет следующий алгоритм:
- Выбрать случайное целое число \(x\) равновероятно в диапазоне от \(1\) до \(m\) и добавить в конец \(a\).
- Вычислить наибольший общий делитель чисел в массиве \(a\).
- Если он равен \(1\), то закончить.
- Иначе продолжить с шага \(1\).
Найдите математическое ожидание длины массива \(a\). Можно показать, что его можно представить как \(\frac{P}{Q}\), где \(P\) и \(Q\) взаимнопростые целые числа и \(Q\neq 0 \pmod{10^9+7}\). Выведите значение \(P \cdot Q^{-1} \pmod{10^9+7}\).
Выходные данные
Выведите одно целое число — математическое ожидание длины массива \(a\) как \(P \cdot Q^{-1} \pmod{10^9+7}\).
Примечание
В первом примере Вивек может добавлять только числа в диапазоне от \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
|
|
2
|
2
|
2
|
|
3
|
4
|
333333338
|