分数: 800 点
问题陈述
给定的是一系列 A+B 整数 (X_1,X_2,\cdots,X_{A+B}),其中恰好包含 A 和完全一样 B 两点。
Snuke 有一套 s,最初是空的。 他要做的 A+B 操作。 的 i第操作如下。
-
If X_i=1: 选择一个整数 v 这样 1 \leq v \leq A 并将其添加到 s。 在这里, v 不得是在先前操作中选择的整数。
-
If X_i=2:删除自 s 具有最大值的元素。 输入保证 在此操作之前 s 不为空。
有多少组可以成为最终状态 s? 求计数模数 998244353.
约束
- 1 \leq A \leq 5000
- 0 \leq B \leq A-1
- 1 \leq X_i \leq 2
- X_i=1 正是 A 指数 i.
- X_i=2 正是 B 指数 i.
- s 在执行以下操作之前不会为空 X_i=2.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
A B
X_1 X_2 \cdots X_{A+B}
输出
打印答案模数 998244353.
样本输入 1
3 1 1 1 2 1
示例输出 1
2
有两种可能的最终状态 s: s=\{1,2\},\{1,3\}.
例如,以下操作序列会产生 s=\{1,3\}.
- i=1:添加 2 to s.
- i=2:添加 1 to s.
- i=3:删除 2 来自 s.
- i=4:添加 3 to s.
示例输入 2
20 6 1 1 1 1 1 2 1 1 1 2 1 2 1 2 1 2 1 1 1 1 2 1 1 1 1 1
示例输出 2
5507