分数: 600 点
问题陈述
对于序列 X 由有限个非负整数组成,我们定义 \mathrm{mex}(X) 作为不在其中的最小非负整数 X。例如, \mathrm{mex}((0,0, 1,3)) = 2, \mathrm{mex}((1)) = 0, \mathrm{mex}(()) = 0.
给你一个序列 S=(S_1,\ldots,S_N) 长度 N 其中每个元素是 0 or 1.
求模数 998244353,序列 A=(A_1,A_2,\ldots,A_N) 长度 N 由之间的整数组成 0 和 M,包含在内,满足以下条件:
- 对于每个 i (1\leq i\leq N), A_i = \mathrm{mex}((A_1,A_2,\ldots,A_{i-1})) if S_i=1,和 A_i \neq \mathrm{mex}((A_1,A_2,\ldots,A_{i-1})) if S_i=0.
约束
- 1 \leq N \leq 5000
- 0 \leq M \leq 10^9
- S_i is 0 or 1.
- 所有输入数字均为整数。
输入
输入由标准输入按以下格式给出:
N M S_1 \ldots S_N
输出
打印答案。
示例输入 1
4 2 1 0 0 1
示例输出 1
4
以下四个序列满足条件:
- (0,0,0,1)
- (0,0,2,1)
- (0,2,0,1)
- (0,2,2,1)
示例输入 2
10 1000000000 0 0 1 0 0 0 1 0 1 0
示例输出 2
587954969
一定要找到计数模数 998244353.