← 返回题目列表

AtCoder · agc021_f

F. 三位一体

中文机器翻译题面 查看原题

分数: 1800 点

问题陈述

我们有一个 N \times M 网格。广场位于 i第行和 j第列将表示为 (i,j)。 特别是,左上角的方块将表示为 (1,1),右下方块将表示为 (N,M)。 高桥将一些方块(可能是零)涂成黑色,并将其他方块涂成白色。

我们将定义一个整数序列 A 长度 N,和两个整数序列 B 和 C 长度 M 各,如下:

  • A_i(1\leq i\leq N) 是最小值 j 这样 (i,j) 被涂成黑色,或者 M+1 如果不存在。
  • B_i(1\leq i\leq M) 是最小值 k 这样 (k,i) 被涂成黑色,或者 N+1 如果不存在。
  • C_i(1\leq i\leq M) 是最大值 k 这样 (k,i) 被涂成黑色,或者 0 如果不存在。

有多少个三元组 (A,B,C) 会发生吗?求计数模数 998244353.

通知

在这个问题中,你的源代码的长度必须最多为 20000 B. 请注意,超过最大长度的提交内容将被视为无效。


约束

  • 1 \leq N \leq 8000
  • 1 \leq M \leq 200
  • N 和 M 是整数。

部分分数 通过满足以下条件的测试集将获得

  • 1500 积分 N\leq 300.

输入

输入由标准输入按以下格式给出:

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^M=64.


示例输入 2

4 3

示例输出 2

2588

示例输入 3

17 13

示例输出 3

229876268

示例输入 4

5000 100

示例输出 4

57613837