题目描述

给定一个长度为 $A+B$ 的整数序列 $(X_1,X_2,\cdots,X_{A+B})$。$X$ 恰好包含 $A$ 个 $1$ 和 $B$ 个 $2$。

すぬけくん有一个集合 $s$，最开始 $s$ 为空。他将进行 $A+B$ 次操作，第 $i$ 次操作如下：

• 当 $X_i=1$ 时：选择一个满足 $1\leq v\leq A$ 的整数 $v$，并将其加入 $s$。但之前已经选择过的整数不能再次选择为 $v$。
• 当 $X_i=2$ 时：从 $s$ 中删除当前的最大元素。保证在进行该操作前，$s$ 不为空。

请问最终可能得到多少种不同的 $s$ 集合？请将答案对 $998244353$ 取模后输出。

输入格式

输入通过标准输入给出，格式如下：

$A$ $B$ $X_1$ $X_2$ $\cdots$ $X_{A+B}$

输出格式

输出一个整数，表示最终可能得到的不同 $s$ 集合的数量，对 $998244353$ 取模。

样例 1

输入

3 1
1 1 2 1

输出

2

样例 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

输出

5507

说明/提示

限制条件

• $1\leq A\leq 5000$
• $0\leq B\leq A-1$
• $1\leq X_i\leq 2$
• 恰好有 $A$ 个 $i$ 满足 $X_i=1$。
• 恰好有 $B$ 个 $i$ 满足 $X_i=2$。
• 每次进行 $X_i=2$ 的操作前，$s$ 都不为空。
• 输入的所有值均为整数。

样例解释 1

最终可能的 $s$ 集合有 $s=\{1,2\}$ 和 $s=\{1,3\}$ 共 $2$ 种。例如，按如下方式操作，最终 $s=\{1,3\}$：

• $i=1$：向 $s$ 中加入 $2$。
• $i=2$：向 $s$ 中加入 $1$。
• $i=3$：从 $s$ 中删除 $2$。
• $i=4$：向 $s$ 中加入 $3$。

由 ChatGPT 4.1 翻译