B. Разрезание перестановки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$n$$$ и массив $$$a$$$ длины $$$n-1$$$.

Для перестановки$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$ определим

$$$$$$ v_i=\min\left(\max_{1\le j\le i}p_j, \max_{i+1\le j\le n}p_j\right), $$$$$$

где $$$1\le i\le n-1$$$.

Иными словами, разрежьте перестановку между позициями $$$i$$$ и $$$i+1$$$, возьмите максимальный элемент с каждой стороны и задайте $$$v_i$$$ равным меньшему из этих двух значений.

Ваша задача — посчитать количество перестановок $$$p$$$ длины $$$n$$$ таких, что $$$v_i=a_i$$$ для каждого $$$1\le i\le n-1$$$.

Ответ выведите по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

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

В первой строке каждого набора входных данных дано одно целое число $$$n$$$ ($$$2\le n\le 10^6$$$) — длина $$$p$$$.

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

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

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

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

Пример
Входные данные
11
2
1
3
2 2
3
1 1
4
2 3 2
5
3 3 4 2
2
2
3
1 2
4
3 3 3
5
4 4 4 4
4
2 1 2
6
3 3 5 5 5
Выходные данные
2
2
0
0
2
0
2
4
12
0
8
Примечание

В первом наборе входных данных обе перестановки $$$[1,2]$$$ и $$$[2,1]$$$ удовлетворяют условию $$$v_1=1$$$.

Во втором наборе входных данных единственные подходящие перестановки — это $$$[2,1,3]$$$ и $$$[3,1,2]$$$.

В третьем наборе входных данных подходящей перестановки не существует.