Найдите количество способов, которыми можно построить строку длины n используя k латинских букв (размер алфавита равен k) в виде конкатенации двух непустых палиндромов.
Два натуральных числа n и k (1≤n≤105,1≤k≤26).
Выведите количество способов построить заданную строку. Ответ вывести по модулю 109+7.
В первом примере строку длины 4 из одной буквы (а например) можно построить тремя способами: a+aaa,aa+aa,aaa+a.