Для тех, кто еще не понял: этой зимой в городе XXXводске реально холодно! Настолько холодно, что в голову порой лезут странные мысли. Например, сколько существует строк длины ровно n, над алфавитом размера m, таких, что любая подстрока длины в точности k является палиндромом. Ваша задача — найти это количество по модулю 1000000007 (109 + 7). Смотрите не упустите ни одной!
Напоминаем, что подстрока является палиндромом, если она одинаково читается как слева направо, так и справа налево.
Выходные данные
Выведите одно целое число — количество строк описанного вида по модулю 1000000007 (109 + 7).
Примечание
В первом примере допустимой является только одна строка: «a» (обозначим как «a» единственную букву нашего алфавита).
Во втором примере (если обозначить буквы алфавита как «a» и «b») допустимы следующие строки: «aaaaa» и «bbbbb».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 1
|
1
|
|
2
|
5 2 4
|
2
|