Задачи
Конкатенация двух палиндромов
Конкатенация двух палиндромов
Найдите количество способов, которыми можно построить строку длины $n$ используя $k$ латинских букв (размер алфавита равен $k$) в виде конкатенации двух непустых палиндромов.
\InputFile
Два натуральных числа $n$ и $k~(1 \le n \le 10^5, 1 \le k \le 26)$.
\OutputFile
Выведите количество способов построить заданную строку. Ответ вывести по модулю $10^9 + 7$.
\Examples
В первом примере строку длины $4$ из одной буквы ($а$ например) можно построить тремя способами: $a + aaa, aa + aa, aaa + a$.
Входные данные #1
4 1
Выходные данные #1
3
Входные данные #2
3 2
Выходные данные #2
8