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

В ряд стоят $$$n$$$ волшебников, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. У каждого волшебника есть плащ-невидимка, который можно носить либо с левой стороны, либо с правой. Гарри идет от позиции волшебника $$$1$$$ до позиции волшебника $$$n$$$ ($$$1 \le n \le 10^5$$$) и фиксирует, сколько волшебников он видит с каждой позиции. Волшебник на позиции $$$j$$$ виден с позиции $$$i$$$, если:

  • Волшебник $$$j$$$ носит свой плащ с левой стороны и $$$i \ge j$$$.
  • Волшебник $$$j$$$ носит свой плащ с правой стороны и $$$i \le j$$$.

В частности, обратите внимание, что волшебник $$$i$$$ всегда виден с позиции $$$i$$$.

Список Гарри очень старый, но после долгих усилий вам удалось его расшифровать. Список представляет собой массив $$$a$$$ из $$$n$$$ элементов, где $$$i$$$-й элемент $$$a_i$$$ ($$$1 \le a_i \le n$$$) — это количество волшебников, которых Гарри видел с позиции волшебника $$$i$$$.

Ваша задача — определить, сколько из всех возможных расположений плащей соответствуют данным, зафиксированным в списке. Выведите ответ по модулю $$$676\,767\,677$$$.

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива $$$a$$$.

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

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

Для каждого набора входных данных выведите одно целое число — количество расположений плащей волшебников, которые удовлетворяют условию, по модулю $$$676\,767\,677$$$.

Пример
Входные данные
7
1
1
4
4 4 3 2
3
1 3 2
2
2 1
3
2 2 2
3
3 2 3
3
3 2 2
Выходные данные
2
1
0
1
2
0
0
Примечание

На изображении ниже показано расположение плащей, которое соответствует списку Гарри во втором наборе входных данных.

Волшебник 1 носит плащ-невидимку с левой стороны, в то время как волшебники $$$2$$$, $$$3$$$ и $$$4$$$ носят его с правой стороны.

  • С позиции $$$1$$$ мы можем видеть волшебников $$$1$$$, $$$2$$$, $$$3$$$ и $$$4$$$.
  • С позиции $$$2$$$ мы можем видеть волшебников $$$1$$$, $$$2$$$, $$$3$$$ и $$$4$$$.
  • С позиции $$$3$$$ мы можем видеть волшебников $$$1$$$, $$$3$$$ и $$$4$$$.
  • С позиции $$$4$$$ мы можем видеть волшебников $$$1$$$ и $$$4$$$.

Таким образом, список Гарри оказывается $$$[4, 4, 3, 2]$$$. Можно доказать, что это единственное возможное расположение плащей.

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

В пятом наборе входных данных обратите внимание, что существует два возможных расположения плащей, из которых Гарри мог получить свой список:

  • $$$1 \mid \quad \mid 2 \quad 3 \, \mid$$$
  • $$$\mid \, 1 \quad 2 \mid \quad \mid 3$$$