← 返回题目列表

AtCoder · utpc2023_d

D. DRD 字符串

中文机器翻译题面 查看原题

配点 : 100 点

問題文

一个非空字符串 D, R(两者可以相同)来表示 S = D + R + D 时,字符串 S 是 您也可以写 被称为 DRD 字符串。这里,+ 表示字符串的连接。

当可使用的字符有 M 种时,长度为 N 的 DRD 字符串可以考虑的数量为 998244353 除的余数。

制約

  • 所有输入均为整数
  • 3 \leq N \leq 10^6
  • 1 \leq M \leq 10^6

入力

输入是按以下格式从标准输入给出的。

N M

出力

答案 请打印除以 1 行输出。


入力例 1

6 2

出力例 1

40

可使用的 2 种字符 a, b 。例如 abbaab, aaaaaa 是长度, 请以 6 是 DRD 字符串。另一方面,abbabb, aaabbb 不是 DRD 字符串。


入力例 2

3017 7801

出力例 2

515391664