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 翻译