AT_arc170_c [ARC170C] Prefix Mex Sequence

[problemUrl]: https://atcoder.jp/contests/arc170/tasks/arc170_c 有限個の非負整数からなる数列 $ 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})) $

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ S_1 $ $ \ldots $ $ S_N $

答えを出力せよ．

### 制約 - $ 1\ \leq\ N\ \leq\ 5000 $ - $ 0\leq\ M\leq\ 10^9 $ - $ S_i $ は $ 0 $ または $ 1 $ - 入力される数値は全て整数 ### Sample Explanation 1 条件を満たす数列は以下の $ 4 $ 個です． - $ (0,0,0,1) $ - $ (0,0,2,1) $ - $ (0,2,0,1) $ - $ (0,2,2,1) $ ### Sample Explanation 2 個数を $ 998244353 $ で割ったあまりを求めることに注意してください．