eolymp
Змагання

Комбинаторика. Формула

Конкатенация двух палиндромов

Найдите количество способов, которыми можно построить строку длины n используя k латинских букв (размер алфавита равен k) в виде конкатенации двух непустых палиндромов.

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

Два натуральных числа n и k (1n105, 1k26).

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

Выведите количество способов построить заданную строку. Ответ вывести по модулю 109 + 7.

Пояснение

В первом примере строку длины 4 из одной буквы (а например) можно построить тремя способами: a + aaa, aa + aa, aaa + a.

Ліміт часу 2 секунди
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 1
Вихідні дані #1
3
Вхідні дані #2
3 2
Вихідні дані #2
8