← 返回题目列表

AtCoder · arc170_c

C. 前缀 Mex 序列

中文机器翻译题面 查看原题

分数: 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.