# 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** (**1** ≤ **n** ≤ `10`

, ^{5}**1** ≤ **k** ≤ **26**) - 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**.

3 3

33

6 2

114

42 7

83419789