Вам задано перестановку $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]$.
Це єдині досяжні масиви.