Вам дана перестановка $P$ множества $\{1, 2, \dots, N\}$.
То есть $P$ — это массив длины $N$, содержащий каждое целое число от $1$ до $N$ ровно один раз.
Вы можете выполнять над ним следующую операцию:
- Выбрать индекс $i$ ($1 < i < |P|$).
- Присвоить $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Удалить $P_{i-1}$ и $P_{i+1}$ из $P$. Оставшиеся элементы затем перенумеровываются, начиная с $1$.
Каждая такая операция уменьшает длину $P$ на $2$. В частности, если длина $P$ равна $1$ или $2$, то эту операцию применить нельзя.
Найдите количество различных массивов, которые можно получить, выполнив эту операцию ноль или более раз, начиная с $P$.
Так как это значение может быть большим, вам нужно найти его только по модулю $998\,244\,353$.
Входные данные
Входные данные даны в следующем формате:
T N P_1 P_2 ... P_N ...
Ограничения
- Все входные значения являются целыми числами.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ для всех $i \ne j$.
- Гарантируется, что сумма $N^2$ по всем наборам входных данных не превышает $5000^2$.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество различных массивов, которые можно получить, выполнив операцию ноль или более раз над $P$, по модулю $998\,244\,353$.
Пример
Входные данные 1
5 2 2 1 3 2 1 3 5 3 1 4 5 2 10 1 2 3 4 5 6 7 8 9 10 15 5 7 6 12 2 13 10 1 11 4 3 9 14 15 8
Выходные данные 1
1 2 5 55 365
Примечание
Тестовый пример 1: Никаких операций выполнить нельзя.
Тестовый пример 2: Есть две возможности:
- Не выполнять никаких операций. Итоговый массив равен $[2, 1, 3]$.
- Выполнить одну операцию с $i = 2$. Итоговый массив равен $[3]$.
Это единственные достижимые массивы.