Double Palindrome
시간 제한2초메모리 제한512 MB
처음 k개 알파벳으로 만든 길이 n 이하의 문자열 중 회문이거나 회문 두 개를 이어 붙인 문자열의 개수를 998244353으로 나눈 나머지를 구한다.
문제
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.
입력
The only line contains two integers n and k — the maximum length of the string and the size of the alphabet (1 ≤ n ≤ 105; 1 ≤ k ≤ 26).
출력
Output the number of non-empty double palindromes of length at most n composed of the first k English letters, modulo 998 244 353.
힌트
In the first example the strings to be counted are: a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba, abb, aca, acc, baa, bab, bba, bbb, bbc, bcb, bcc, caa, cac, cbb, cbc, cca, ccb, ccc.