Кевин увлекается логическими головоломками.
Он играет в игру с \(n\) одноклассниками, которые стоят в очереди. \(i\)-й человек слева заявляет, что слева от него (не включая его самого) находится \(a_i\) лжецов.
Каждый одноклассник либо рыцарь, либо лжец, с тем ограничением, что два лжеца не могут стоять рядом друг с другом. Одноклассники-рыцари всегда говорят правду. Лжецы могут говорить либо правду, либо ложь, то есть их заявления недостоверны.
Кевин хочет определить количество различных возможных конфигураций рыцарей и лжецов по модулю \(998\,244\,353\). Две конфигурации считаются различными, если по крайней мере один одноклассник является рыцарем в одной конфигурации и лжецом в другой.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество различных конфигураций по модулю \(998\,244\,353\).
Примечание
Мы будем использовать \(\color{red}{\text{красный}}\) для обозначения лжецов и \(\color{blue}{\text{синий}}\) для обозначения рыцарей.
В первом наборе входных данных единственной возможной конфигурацией является \((\color{red}{0},\color{blue}{1},\color{red}{2})\).
Во втором наборе входных данных возможны две конфигурации: \((\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0})\) и \((\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{red}{0})\).
В третьем наборе входных данных возможны три конфигурации: \((\color{blue}{0},\color{blue}{0},\color{red}{1},\color{blue}{1},\color{red}{2})\), \((\color{blue}{0},\color{red}{0},\color{blue}{1},\color{red}{1},\color{blue}{2})\) и \((\color{blue}{0},\color{red}{0},\color{blue}{1},\color{blue}{1},\color{red}{2})\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
3
0 1 2
5
0 0 0 0 0
5
0 0 1 1 2
5
0 1 2 3 4
5
0 0 1 1 1
5
5 1 5 2 5
1
0
4
2 3 1 1
|
1
2
3
0
4
1
2
0
|