[AGC021F] Trinity

- 现有一个 $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$。

[problemUrl]: https://atcoder.jp/contests/agc021/tasks/agc021_f 縦 $ 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 $ で割った余りを出力せよ。

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 $ 通りです。