F - Trinity Editorial /

Time Limit: 6 sec / Memory Limit: 256 MB

配点 : 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 で割った余りを出力せよ。

入力例 1

2 3

出力例 1

64

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

入力例 2

4 3

出力例 2

2588

入力例 3

17 13

出力例 3

229876268

入力例 4

5000 100

出力例 4

57613837

Score : 1800 points

Problem Statement

We have an N \times M grid. The square at the i-th row and j-th column will be denoted as (i,j). Particularly, the top-left square will be denoted as (1,1), and the bottom-right square will be denoted as (N,M). Takahashi painted some of the squares (possibly zero) black, and painted the other squares white.

We will define an integer sequence A of length N, and two integer sequences B and C of length M each, as follows:

  • A_i(1\leq i\leq N) is the minimum j such that (i,j) is painted black, or M+1 if it does not exist.
  • B_i(1\leq i\leq M) is the minimum k such that (k,i) is painted black, or N+1 if it does not exist.
  • C_i(1\leq i\leq M) is the maximum k such that (k,i) is painted black, or 0 if it does not exist.

How many triples (A,B,C) can occur? Find the count modulo 998244353.

Notice

In this problem, the length of your source code must be at most 20000 B. Note that we will invalidate submissions that exceed the maximum length.

Constraints

  • 1 \leq N \leq 8000
  • 1 \leq M \leq 200
  • N and M are integers.

Partial Score

  • 1500 points will be awarded for passing the test set satisfying N\leq 300.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number of triples (A,B,C), modulo 998244353.

Sample Input 1

2 3

Sample Output 1

64

Since N=2, given B_i and C_i, we can uniquely determine the arrangement of black squares in each column. For each i, there are four possible pairs (B_i,C_i): (1,1), (1,2), (2,2) and (3,0). Thus, the answer is 4^M=64.

Sample Input 2

4 3

Sample Output 2

2588

Sample Input 3

17 13

Sample Output 3

229876268

Sample Input 4

5000 100

Sample Output 4

57613837