AT_arc170_c [ARC170C] Prefix Mex Sequence

对于一个由有限个非负整数组成的数列 $X$，定义 $\mathrm{mex}(X)$ 为不属于 $X$ 的最小非负整数。例如，$\mathrm{mex}((0,0,1,3))=2$，$\mathrm{mex}((1))=0$，$\mathrm{mex}(())=0$。 给定一个长度为 $N$ 的数列 $S=(S_1,\ldots,S_N)$，其中每个元素 $S_i$ 都是 $0$ 或 $1$。 请计算满足以下条件的长度为 $N$ 的数列 $A=(A_1,A_2,\ldots,A_N)$ 的个数，并对 $998244353$ 取模： - $A$ 的每个元素都是 $0$ 到 $M$ 之间的整数（包含 $0$ 和 $M$）。 - 对于每个 $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$ $S_2$ $\ldots$ $S_N$

输出满足条件的数列个数对 $998244353$ 取模的结果。

### 限制条件 - $1\leq N\leq 5000$ - $0\leq M\leq 10^9$ - $S_i$ 为 $0$ 或 $1$ - 输入的所有数均为整数 ### 样例解释 1 满足条件的数列共有 $4$ 个： - $(0,0,0,1)$ - $(0,0,2,1)$ - $(0,2,0,1)$ - $(0,2,2,1)$ ### 样例解释 2 请注意，答案需要对 $998244353$ 取模。 由 ChatGPT 4.1 翻译