题目描述

$n$ 个同学排成一行进行一场游戏；
从左边数第 $i$ 个人说：他左边有 $a_{i}$ 个说谎者（不包括他们自己）；
每个同学要么诚实，要么是说谎者；
没有两个说谎者站在一起；
诚实的同学总是说真话，说谎者可以说真话或谎言，因此他们的陈述可被认为是不可靠的。
你想要确定不同的合法情况数量，结果对 $998244353$ 取模。
如果至少有一个同学在某种情况中是诚实的，而在另一个情况中是说谎者，则这两个情况视为不同。

输入格式

从 $lie.in$ 读入数据。
第一行两个整数 $n,c$，$n$ 含义见题目描述，$c$ 为子任务编号，
接下来一行 $n$ 个整数，描述 $a$ 数组。

输出格式

输出答案到 $lie.out$。
输出一个整数表示不同合法情况的数量，对 $998244353$ 取模。

样例

我们将用 $\color{red} {\text{红色}}$ 来标记说谎者，用 $\color{blue} {\text{蓝色}}$ 来标记诚实的人。

3 4
0 1 2

1

唯一的可能是 $\color{grey}(\color{red}{0},\color{blue}{1},\color{red}{2}\color{grey})$

5 4
0 0 1 1 2

3

三种可能的情况分别是：$\color{grey}(\color{blue}{0},\color{blue}{0},\color{red}{1},\color{blue}{1},\color{red}{2} \color{grey})$, $\color{grey}(\color{blue}{0},\color{red}{0},\color{blue}{1},\color{red}{1},\color{blue}{2}\color{grey})$, $\color{grey}(\color{blue}{0},\color{red}{0},\color{blue}{1},\color{blue}{1},\color{red}{2}\color{grey})$

5 4
0 1 2 3 4

0

5 4
0 0 1 1 1

4

5 4
5 1 5 2 5

1

1 1
0

2

4 4
2 3 1 1

0

见下发文件

见下发文件

下发文件.zip

子任务与数据范围

对于所有数据，保证 $1\leq n\leq 2\times {10}^5,~0\leq a_{i}\leq n$，
测评使用捆绑测试，本题不卡常，短时限是为了防止卡评测。