E. Очередная задача на матожидание
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны целые числа $$$n$$$, $$$k$$$. Рассмотрим алфавит из $$$k$$$ различных символов.

Назовем красотой $$$f(s)$$$ строки $$$s$$$ количество таких индексов $$$i$$$, $$$1\le i<|s|$$$, что префикс $$$s$$$ длины $$$i$$$ равен суфиксу $$$s$$$ длины $$$i$$$. К примеру, красота строки $$$abacaba$$$ равна $$$2$$$, так как для $$$i = 1, 3$$$ префикс и суфикс длины $$$i$$$ совпадают.

Рассмотрим все слова длины $$$n$$$ в данном алфавите. Найдите матожидание $$$f(s)^2$$$ выбранного случайно и равновероятно слова алфавита. Можно показать, что ее можно представить в виде $$$\frac{P}{Q}$$$, где $$$P$$$ и $$$Q$$$ взаимно простые, и $$$Q$$$ не делится на $$$10^9 + 7$$$. Выведите $$$P\cdot Q^{-1} \bmod 10^9 + 7$$$.

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

Первая и единственная строка содержит два числа $$$n$$$, $$$k$$$ ($$$1\le n \le 10^5$$$, $$$1\le k\le 10^9$$$) — длина строки и размер алфавита соответственно.

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

Выведите единственное число — $$$P\times Q^{-1} \bmod 10^9 + 7$$$.

Примеры
Входные данные
2 3
Выходные данные
333333336
Входные данные
1 5
Выходные данные
0
Входные данные
100 1
Выходные данные
9801
Входные данные
10 10
Выходные данные
412377396
Примечание

В первом примере, существует $$$9$$$ слов $$$2$$$ в алфавите размера $$$3$$$ — $$$aa$$$, $$$ab$$$, $$$ac$$$, $$$ba$$$, $$$bb$$$, $$$bc$$$, $$$ca$$$, $$$cb$$$, $$$cc$$$. У $$$3$$$ из них красота $$$1$$$ и у $$$6$$$ из них красота $$$0$$$, поэтому среднее значение равно $$$\frac{1}{3}$$$.

В третьем примере, существует только одно такое слово, и его красота равна $$$99$$$, поэтому среднее значение равно $$$99^2$$$.