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

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

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

Два натуральных числа $n$ и $k(1\le n\le 10^5,1\le k\le 26)$.

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

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

Примеры

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