e-olymp

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

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

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

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

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

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

Пояснение

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4 1
Выходные данные #1
3
Входные данные #2
3 2
Выходные данные #2
8