题目描述

对于一个由有限个非负整数组成的数列 $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

输入

4 2
1 0 0 1

输出

4

样例 2

输入

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

输出

587954969

说明/提示

限制条件

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