Конкатенація двох паліндромів#9592
Знайдіть кількість способів побудувати рядок довжини , використовуючи латинських літер (розмір алфавіту дорівнює ), у вигляді конкатенації двох непорожніх паліндромів.
Дано два натуральних числа і k~(1 \le n \le 10^5, 1 \le k \le 26).
Виведіть кількість способів побудувати такий рядок. Відповідь виведіть за модулем 10^9 + 7.
У першому прикладі рядок довжини , що складається з однієї літери (наприклад, ), можна побудувати трьома способами: a + aaa, aa + aa, aaa + a.
Приклад 1
Приклад 2