前缀 MEX 序列

时间限制：2s
空间限制：1024MB

题目描述

对于一个有限非负整数序列 $X$，定义 $\operatorname{mex}(X)$ 为没有在 $X$ 中出现的最小非负整数。例如 $\operatorname{mex}(0,0,1,3)=2$，空序列的 MEX 为 $0$。

给定一个长度为 $N$ 的 $01$ 序列 $S=(S_1,S_2,\ldots,S_N)$。求有多少个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 满足 $0\le A_i\le M$，且对每个 $i$：

• 若 $S_i=1$，则 $A_i=\operatorname{mex}(A_1,A_2,\ldots,A_{i-1})$；
• 若 $S_i=0$，则 $A_i\ne\operatorname{mex}(A_1,A_2,\ldots,A_{i-1})$。

答案对 $998244353$ 取模。

输入格式

第一行两个整数 $N,M$。

第二行 $N$ 个整数 $S_1,S_2,\ldots,S_N$。

输出格式

输出答案对 $998244353$ 取模后的结果。

样例输入 1

4 2
1 0 0 1

样例输出 1

4

样例输入 2

10 1000000000
0 0 1 0 0 0 1 0 1 0

样例输出 2

587954969

数据范围

• $1\le N\le5000$；
• $0\le M\le10^9$；
• $S_i\in\{0,1\}$。