/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
有限個の非負整数からなる数列 X に対して，\mathrm{mex}(X) を X に含まれない最小の非負整数と定義します．例えば，\mathrm{mex}((0,0, 1,3)) = 2, \mathrm{mex}(( 1) ) = 0, \mathrm{mex}(() ) = 0 です．
各要素が 0 または 1 である長さ N の数列 S=(S_1,\ldots,S_N) が与えられます．
0 以上 M 以下の整数からなる長さ N の数列 A=(A_1,A_2,\ldots,A_N) であって，以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください．
- 各 i(1\leq i\leq N) について，S_i=1 ならば A_i = \mathrm{mex}((A_1,A_2,\ldots,A_{i-1}))，S_i=0 ならば A_i \neq \mathrm{mex}((A_1,A_2,\ldots,A_{i-1}))
制約
- 1 \leq N \leq 5000
- 0\leq M\leq 10^9
- S_i は 0 または 1
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる．
N M S_1 \ldots S_N
出力
答えを出力せよ．
入力例 1
4 2 1 0 0 1
出力例 1
4
条件を満たす数列は以下の 4 個です．
- (0,0,0,1)
- (0,0,2,1)
- (0,2,0,1)
- (0,2,2,1)
入力例 2
10 1000000000 0 0 1 0 0 0 1 0 1 0
出力例 2
587954969
個数を 998244353 で割ったあまりを求めることに注意してください．
Score: 600 points
Problem Statement
For a sequence X composed of a finite number of non-negative integers, we define \mathrm{mex}(X) as the smallest non-negative integer not in X. For example, \mathrm{mex}((0,0, 1,3)) = 2, \mathrm{mex}((1)) = 0, \mathrm{mex}(()) = 0.
You are given a sequence S=(S_1,\ldots,S_N) of length N where each element is 0 or 1.
Find the number, modulo 998244353, of sequences A=(A_1,A_2,\ldots,A_N) of length N consisting of integers between 0 and M, inclusive, that satisfy the following condition:
- For each i (1\leq i\leq N), A_i = \mathrm{mex}((A_1,A_2,\ldots,A_{i-1})) if S_i=1, and A_i \neq \mathrm{mex}((A_1,A_2,\ldots,A_{i-1})) if S_i=0.
Constraints
- 1 \leq N \leq 5000
- 0 \leq M \leq 10^9
- S_i is 0 or 1.
- All input numbers are integers.
Input
The input is given from Standard Input in the following format:
N M S_1 \ldots S_N
Output
Print the answer.
Sample Input 1
4 2 1 0 0 1
Sample Output 1
4
The following four sequences satisfy the conditions:
- (0,0,0,1)
- (0,0,2,1)
- (0,2,0,1)
- (0,2,2,1)
Sample Input 2
10 1000000000 0 0 1 0 0 0 1 0 1 0
Sample Output 2
587954969
Be sure to find the count modulo 998244353.