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

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

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

Входные данные

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

Выходные данные

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