#308. 【NFLSPC #1】String

题目类型:传统型 时间限制:2000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

对于一个字符集 $\Sigma$ 上的字符串 $S$,定义删去 $S$ 中的两个相邻且相同的字符为一次操作。

现字符集的大小 $\lvert \Sigma\rvert = m$。试求 $\Sigma$ 上长度为 $n$ 且能通过若干次操作得到空串的字符串个数。答案对 $998244353$ 取模。

比如字符集 $\Sigma = \{\text a, \text b, \text c\}$ 时,abbcca 符合上述条件而 abbca 不符合。

输入格式

一行,两个整数 $n$ , $m$,由空格分隔。

输出格式

一行,符合条件的字符串个数对 $998244353$ 取模的结果。

样例输入

6 3

样例输出

87

数据规模与约定

对于所有数据,$1 \leq n \leq 250000, 1 \leq m \leq 10^9$。

  • 对于子任务 $1$($\ \ 5\%$),$m = 1$;
  • 对于子任务 $2$($10\%$),$n \leq 10, m \leq 10$;
  • 对于子任务 $3$($20\%$),$n \leq 5000, m = 2$;
  • 对于子任务 $4$($20\%$),$n \leq 1000$;
  • 对于子任务 $5$($15\%$),$n \leq 5000$;
  • 对于子任务 $6$($\ \ 5\%$),$m = 2$;
  • 对于子任务 $7$($\ \ 5\%$),$m = 3$;
  • 对于子任务 $8$($\ \ 5\%$),$n = 149986, m = 2333$;
  • 对于子任务 $9$($15\%$),无特殊限制。

$by\ \text{djq_cpp}$