Double Palindrome#9521
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 composed of the first English letters have the same property. Help her find this number and output it modulo .
The only line contains two integers and (1 \le n \le 10^5, 1 \le k \le 26) - the maximum length of the string and the size of the alphabet.
Output the number of non-empty double palindromes of length at most composed of the first English letters, modulo .
Example 1
Example 2
Example 3