题目描述

回文串是正着读和倒着读完全相同的字符串。例如 rotator、lil 和 abba 都是回文串，而 shalash 不是。

定义一个字符串为 双重回文串，当且仅当它满足下列条件之一：

1. 它本身是回文串；
2. 它可以表示成两个回文串的连接，这两个回文串不要求不同。

例如，susanna、potato 和 abba 都是双重回文串，而 zzyzx 和 abaabb 不是。

给定最大长度 $n$ 和字母表大小 $k$，考虑只由前 $k$ 个英文字母组成的所有非空字符串。

求长度不超过 $n$ 的双重回文串数量，对 $998244353$ 取模。

输入格式

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

其中 $n$ 是字符串最大长度，$k$ 是字母表大小。

输出格式

输出一个整数，表示长度不超过 $n$、由前 $k$ 个英文字母组成的非空双重回文串数量，对 $998244353$ 取模后的结果。

样例

样例 1

3 3

33

样例 2

6 2

114

样例 3

42 7

83419789

说明

样例 1 中需要统计的字符串为：

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。