配点 : $1800$ 点

問題文

縦 $N$ マス、横 $M$ マスのマス目があります。$i$ 行目、$j$ 列目にあるマスを $(i,j)$ とあらわすことにします。 特に、一番左上のマスは $(1,1)$ と、一番右下のマスは $(N,M)$ とあらわされます。 高橋君は $0$ 個以上のいくつかのマスを黒く、他のマスを白く塗りました。

長さ $N$ の数列 $A$ と、長さ $M$ の数列 $B,C$ をそれぞれ以下のように定義するとき、列の組 $(A,B,C)$ としてありうるものの個数を $998244353$ で割った余りを求めてください。

• $A_i(1\leq i\leq N)$ は、マス $(i,j)$ が黒く塗られているような最小の $j$ (存在しない場合、$M+1$)
• $B_i(1\leq i\leq M)$ は、マス $(k,i)$ が黒く塗られているような最小の $k$ (存在しない場合、$N+1$)
• $C_i(1\leq i\leq M)$ は、マス $(k,i)$ が黒く塗られているような最大の $k$ (存在しない場合、$0$)

注意

この問題では、提出できるソースコードのサイズは $20000$ B 以下に制限される。 制限を超える長さの提出は無効とするので注意すること。

制約

• $1 \leq N \leq 8000$
• $1 \leq M \leq 200$
• $N,M$ は整数である

部分点

• $N\leq 300$ を満たすデータセットに正解すると、$1500$ 点が与えられる。

入力

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

N M

出力

列の組 $(A,B,C)$ の個数を $998244353$ で割った余りを出力せよ。

2 3

64

$N=2$ なので、$B_i,C_i$ の情報から、各列の黒く塗られたマスの配置が一意に定まります。各 $i$ について、$(B_i,C_i)$ の組は $(1,1),(1,2),(2,2),(3,0)$ の $4$ 通りなので、答えは $4^M=64$ 通りです。

4 3

2588

17 13

229876268

5000 100

57613837