/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 で割った余りを出力せよ．
入力例 1
3 1 1 1 2 1
出力例 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 を追加する．
入力例 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
Score : 800 points
Problem Statement
Given is a sequence of A+B integers (X_1,X_2,\cdots,X_{A+B}), which contains exactly A ones and exactly B twos.
Snuke has a set s, which is initially empty. He is going to do A+B operations. The i-th operation is as follows.
-
If X_i=1: Choose an integer v such that 1 \leq v \leq A and add it to s. Here, v must not be an integer that was chosen in a previous operation.
-
If X_i=2: Delete from s the element with the largest value. The input guarantees that s is not empty just before this operation.
How many sets are there that can be the final state of s? Find the count modulo 998244353.
Constraints
- 1 \leq A \leq 5000
- 0 \leq B \leq A-1
- 1 \leq X_i \leq 2
- X_i=1 for exactly A indices i.
- X_i=2 for exactly B indices i.
- s will not be empty just before an operation with X_i=2.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B
X_1 X_2 \cdots X_{A+B}
Output
Print the answer modulo 998244353.
Sample Input 1
3 1 1 1 2 1
Sample Output 1
2
There are two possible final states of s: s=\{1,2\},\{1,3\}.
For example, the following sequence of operations results in s=\{1,3\}.
- i=1: Add 2 to s.
- i=2: Add 1 to s.
- i=3: Delete 2 from s.
- i=4: Add 3 to s.
Sample Input 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
Sample Output 2
5507