配点 : $700$ 点

問題文

長さ $N$ の整数の集合の列 $S=(S_1,S_2,\dots,S_N)$ のうち、以下の条件を全て満たすものを「素晴らしい集合の列」と呼びます。

• $S_i$ は $1$ 以上 $M$ 以下の整数のみからなる集合(空集合でもよい)である。$(1 \le i \le N)$
• $S_i$ と $S_{i+1}$ のうち、ちょうど片方にのみ含まれる要素の個数は $1$ 個である。$(1 \le i \le N-1)$

ここで、素晴らしい集合の列 $S$ のスコアを $\displaystyle \prod_{i=1}^{M}$ $(S_1,S_2,\dots,S_N$ のうち、$i$ を含む集合の個数 $)$ と定義します。

全ての素晴らしい集合の列に対するスコアの総和を $998244353$ で割ったあまりを求めてください。

制約

• $1 \le N,M \le 2 \times 10^5$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

出力

答えを出力せよ。

2 3

24

素晴らしい集合の列のうち、スコアが正であるものは以下の $6$ 個です。

• $S_1=\{1,2\},S_2=\{1,2,3\}$
• $S_1=\{1,3\},S_2=\{1,2,3\}$
• $S_1=\{2,3\},S_2=\{1,2,3\}$
• $S_1=\{1,2,3\},S_2=\{1,2\}$
• $S_1=\{1,2,3\},S_2=\{1,3\}$
• $S_1=\{1,2,3\},S_2=\{2,3\}$

全てスコアは $4$ であるため、解は $24$ です。

12 34

786334067