eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Двойные палиндромы

Двойные палиндромы

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Палиндромом называется строка, которая читается вперед и назад одинаково. Например rotator, lil и abba палиндромы, но shalash палиндромом не является.

Двойным палиндромом называется строка, которая является либо палиндромом, либо объединением двух (не обязательно различных) палиндромов. Например susanna, potato и abba - двойные палиндромы, но zzyzx и abaabb таковыми не являются.

Далила только что поняла, что ее имя - двойной палиндром! Теперь ей интересно, сколько непустых строк длины не более n, составленных из первых k английских букв, имеют это свойство. Помогите ей найти это количество и вывести его по модулю 998 244 353.

Вхідні дані

Строка содержит два целых числа n и k (1n10^5, 1k26) - наибольшая длина строки и размер алфавита.

Вихідні дані

Выведите количество непустых двойных палиндромов длины не более n, состоящих из первых k английских букв по модулю 998 244 353.

Приклад

Вхідні дані #1
3 3
Вихідні дані #1
33
Вхідні дані #2
6 2
Вихідні дані #2
114
Вхідні дані #3
42 7
Вихідні дані #3
83419789
Джерело 2019 ACM NEERC, Северный регион, Октябрь 26, Задача D