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

Знайдіть кількість способів побудувати рядок довжини $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$.