이중 회문

시간 제한2초메모리 제한512 MB

요약

길이가 n 이하이고 처음 k개 알파벳으로 이루어진 문자열 가운데 팰린드롬이거나 팰린드롬 두 개를 이은 문자열의 개수를 998244353으로 나눈 나머지로 구합니다.

난이도: 보통10점 중 7점
유형: 문자열, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

회문은 앞에서 읽으나 뒤에서 읽으나 같은 문자열이다. 예를 들어 rotator, lil, abba는 회문이지만 shalash는 회문이 아니다.

이중 회문은 회문이거나, 회문 두 개를 이어 붙인 문자열이다. 두 회문은 서로 같을 수도 있다. 예를 들어 susanna, potato, abba는 이중 회문이지만 zzyzx와 abaabb는 아니다.

Dalila는 자신의 이름이 이중 회문이라는 사실을 방금 알아차렸다. 이제 그녀는 영문 알파벳 앞 k개로 만들 수 있고 길이가 n 이하인 공백이 아닌 문자열 중에서 같은 성질을 가진 것이 몇 개인지 궁금해한다. 그 개수를 구하고, 998 244 353으로 나눈 나머지를 출력하라.

입력

첫 줄에 정수 두 개 n과 k가 주어진다. n은 문자열의 최대 길이이고, k는 알파벳의 크기이다( $1 \le n \le 10^5$ , $1 \le k \le 26$ ).

출력

영문 알파벳 앞 k개로 이루어지고 길이가 n 이하인 공백이 아닌 이중 회문의 개수를 998 244 353으로 나눈 나머지를 출력한다.

힌트

첫 번째 예제에서 세어야 하는 문자열은 다음과 같다: 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.

예제3

예제 1
입력
```
3 3
```
예상 출력
```
33
```
예제 2
입력
```
6 2
```
예상 출력
```
114
```
예제 3
입력
```
42 7
```
예상 출력
```
83419789
```