题目描述

求所有长为 $n$、字符集大小为 $k$ 的字符串的本质不同回文子串数量之和。

答案对 $998244353$ 取模。

输入格式

一行两个整数 $n,k$。

输出格式

一行一个整数，表示答案。

样例 1

样例输入 1

4 2

样例输出 1

64

样例 2

样例输入 2

5 3

样例输出 2

1167

数据范围

对于所有数据，保证：

本题共有 $50$ 个测试点。其中第 $i$ 个测试点满足：

• 若 $i\le 22$，则 $n=2i$；
• 若 $i\ge 23$，则 $n=44+3\times(i-22)$。