D - DRD String
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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