e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

ACM NEERC 2019

Double Palindrome

A palindrome is a string that reads the same backward as forward. For example rotator, lil and abba are palindromes, but shalash is not.

A double palindrome is a string that is either a palindrome or a concatenation of two (not necessarily distinct) palindromes. For example, susanna, potato and abba are double palindromes, but zzyzx and abaabb are not.

Dalila has just realized that her name is a double palindrome! Now she wonders how many non-empty strings of length at most n composed of the first k English letters have the same property. Help her find this number and output it modulo 998 244 353.

Input

The only line contains two integers n and k (1n105, 1k26) - the maximum length of the string and the size of the alphabet.

Output

Output the number of non-empty double palindromes of length at most n composed of the first k English letters, modulo 998 244 353.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 3
Output example #1
33
Input example #2
6 2
Output example #2
114
Input example #3
42 7
Output example #3
83419789
Source 2019 ACM NEERC, Nothern region, October 26, Problem D