字符串

问题描述

一个长度为 $n$ 的字符串 $S$ 是好的，当且仅当存在一个正整数 $k$，满足$2k<n$，且子串 $S[1:k]=S[n-k+1:n]$。

现给定正整数 $n,m$，试求解有多少个长度为 $n$，字符集大小为 $m$ 的好的字符串，答案对 $998244353$ 取模。

输入格式

第一行包含 $2$ 个正整数 $n,m$。

输出格式

输出共 $1$ 行，输出 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

样例输入1

6 2

样例输出1

40

样例解释

如果我们用 $a,b$ 作为字符集，那么 $abbaab,aaaaaa$ 是好的字符串，$baabaa,aaabbb$ 不是好的字符串。

样例输入2

100 24

样例输出2

769330521

样例输入3

100000 24242

样例输出3

969551959

评测数据规模

对于 $10\%$ 的数据，$1 \leq n,m \leq 6$。

对于 $30\%$ 的数据，$1 \leq n,m \leq 20$​​。

对于 $60\%$ 的数据，$1 \leq n,m \leq 10^6$。

对于 $100\%$ 的数据，$1 \leq n,m \leq 5 \times 10^7$。