Подвійні паліндроми#9521
Паліндромом називається рядок, який читається однаково зліва направо і справа наліво. Наприклад, rotator, lil і abba є паліндромами, тоді як shalash не є паліндромом.
Подвійним паліндромом називається рядок, який є або паліндромом, або об'єднанням двох (не обов'язково різних) паліндромів. Наприклад, susanna, potato і abba є подвійними паліндромами, тоді як zzyzx і abaabb такими не є.
Даліла щойно усвідомила, що її ім'я є подвійним паліндромом! Тепер їй цікаво, скільки існує непорожніх рядків довжини не більше , складених з перших літер англійського алфавіту, які мають цю властивість. Допоможіть їй знайти цю кількість і вивести її за модулем .
У рядку містяться два цілі числа і (1 \le n \le 10^5, 1 \le k \le 26) — максимальна довжина рядка і розмір алфавіту.
Виведіть кількість непорожніх подвійних паліндромів довжини не більше , складених з перших літер англійського алфавіту, за модулем .
Приклад 1
Приклад 2
Приклад 3