Даны целые числа \(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\).
Выходные данные
Выведите единственное число — \(P\times Q^{-1} \bmod 10^9 + 7\).
Примечание
В первом примере, существует \(9\) слов \(2\) в алфавите размера \(3\) — \(aa\), \(ab\), \(ac\), \(ba\), \(bb\), \(bc\), \(ca\), \(cb\), \(cc\). У \(3\) из них красота \(1\) и у \(6\) из них красота \(0\), поэтому среднее значение равно \(\frac{1}{3}\).
В третьем примере, существует только одно такое слово, и его красота равна \(99\), поэтому среднее значение равно \(99^2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
|
333333336
|
|
2
|
1 5
|
0
|
|
3
|
100 1
|
9801
|
|
4
|
10 10
|
412377396
|