e-olymp
Yarışlar

Exponentiation

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

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

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

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

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

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

Пояснение

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4 1
Çıxış verilənləri #1
3
Giriş verilənləri #2
3 2
Çıxış verilənləri #2
8