C. Кевин и головоломка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кевин увлекается логическими головоломками.

Он играет в игру с $$$n$$$ одноклассниками, которые стоят в очереди. $$$i$$$-й человек слева заявляет, что слева от него (не включая его самого) находится $$$a_i$$$ лжецов.

Каждый одноклассник либо рыцарь, либо лжец, с тем ограничением, что два лжеца не могут стоять рядом друг с другом. Одноклассники-рыцари всегда говорят правду. Лжецы могут говорить либо правду, либо ложь, то есть их заявления недостоверны.

Кевин хочет определить количество различных возможных конфигураций рыцарей и лжецов по модулю $$$998\,244\,353$$$. Две конфигурации считаются различными, если по крайней мере один одноклассник является рыцарем в одной конфигурации и лжецом в другой.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1\leq n \leq 2 \cdot 10^5$$$) — количество одноклассников.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i \leq n$$$) — количество лжецов слева от $$$i$$$-го человека, о котором они заявили.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество различных конфигураций по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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
Примечание

Мы будем использовать $$$\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})$$$.