I. Воронежини животнини
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Листая ваш любимый сайт с короткими видео, вы наткнулись на ролик «Рейтинг $$$n$$$ лучших воронежских животных, разлагающих мозг». Вам стало очень интересно, от каких же животных мозг лучше всего гниет.

В рейтинг вошли $$$n$$$ воронежских животных, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Обозначим за $$$p_i$$$ номер животного, занимающего $$$i$$$-ю строчку в рейтинге. Гарантируется, что рейтинг включает всех животных, то есть массив $$$p$$$ образует перестановку целых чисел от $$$1$$$ до $$$n$$$.

Автор видео, насмотревшись подобного контента, поступил странным образом. Вместо того чтобы показать в своем видео составленный рейтинг, он поступил иначе. Для каждых двух соседних строчек рейтинга автор рассказал, чему равняется максимум из номеров животных, занимающих эти строчки рейтинга. Более формально, автор видео предоставил вам массив $$$a$$$ длины $$$n - 1$$$, где $$$a_i = \max (p_i, p_{i + 1})$$$ для всех $$$i$$$ от $$$1$$$ до $$$n - 1$$$.

К сожалению, по этой информации не всегда возможно однозначно восстановить исходный рейтинг. Найдите количество способов составить рейтинг животных, который будет согласован с информацией от автора видео.

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

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

Первая строка набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество воронежских животных, вошедших в рейтинг.

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.

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

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

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

В первом наборе входных данных можно составить рейтинг двумя способами: $$$[1, 3, 2]$$$ и $$$[2, 3, 1]$$$.

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