题目描述

縦 $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$)

输入格式

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

$N$ $M$

输出格式

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

题目大意

• 现有一个 $N$ 行 $M$ 列的、仅包含黑白格的表格，左上为 $(1, 1)$，右下为 $(N, M)$。
• 对于一个表格，设长度为 $N$ 的数列 $A$，长度为 $M$ 的数列 $B$、$C$ 分别表示：
  • $A_i$ 表示第 $i$ 行第一个黑格的列号。若不存在则为 $M+1$。
  • $B_i$ 表示第 $i$ 列第一个黑格的行号。若不存在则为 $N+1$。
  • $C_i$ 表示第 $i$ 列最后一个黑格的行号。若不存在则为 $0$。
• 现请你求出所有的 $2^{NM}$ 种表格中，不同的数列三元组 $(A,B,C)$ 的个数对 $998244353$ 取模的结果。
• $1 \leq N \leq 8 \times 10^3$，$1 \leq M \leq 200$。

2 3

64

4 3

2588

17 13

229876268

5000 100

57613837

提示

注意

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

制約

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

部分点

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

Sample Explanation 1

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