Problem Description

$n$ students stand in a line to play a game.
The $i$-th student from the left says: there are $a_{i}$ liars to his left (excluding themselves).
Each student is either honest or a liar.
No two liars stand next to each other.
Honest students always tell the truth, while liars can tell either the truth or lies, so their statements are considered unreliable.
You need to determine the number of distinct possible game configurations, modulo $998244353$.
Two configurations are considered different if at least one student is honest in one configuration and a liar in the other.

Input Format

Read the data from lie.in.

The first line contains two integers $n$ and $c$, where $n$ is as described in the problem, and $c$ is the subtask ID.
The next line contains $n$ integers, describing the array $a$.

Output Format

Output the answer to lie.out.

Output an integer representing the number of distinct possible game configurations, modulo $998244353$.

Samples

We will use $\color{red} {\text{red}}$ to mark liars and $\color{blue} {\text{blue}}$ to mark honest students.

3 4
0 1 2

1

The only possible configuration is $\color{grey}(\color{red}{0},\color{blue}{1},\color{red}{2}\color{grey})$.

5 4
0 0 1 1 2

3

The three possible configurations are: $\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

See the attached file.

See the attached file.

attached file.zip

Subtasks and Constraints

For all data, it is guaranteed that $1\leq n\leq 2\times {10}^5,~0\leq a_{i}\leq n$.
Subtasks are used in this task.