配点 : $800$ 点

問題文

長さ $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$ で割った余りを求めてください．

制約

• $1 \leq A \leq 5000$
• $0 \leq B \leq A-1$
• $1 \leq X_i \leq 2$
• $X_i=1$ を満たす $i$ がちょうど $A$ 個存在する．
• $X_i=2$ を満たす $i$ がちょうど $B$ 個存在する．
• $X_i=2$ の操作を行う直前で $s$ は空ではない．
• 入力される値はすべて整数である．

入力

入力は以下の形式で標準入力から与えられる．

$A$ $B$

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

出力

答えを $998244353$ で割った余りを出力せよ．

3 1
1 1 2 1

2

最終的な $s$ としてありうる状態は，$s=\{1,2\},\{1,3\}$ の $2$ 通りです．

例えば，以下のように操作すると，最終的に $s=\{1,3\}$ となります．

• $i=1$: $s$ に $2$ を追加する．
• $i=2$: $s$ に $1$ を追加する．
• $i=3$: $s$ から $2$ を削除する．
• $i=4$: $s$ に $3$ を追加する．

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