Se te da una permutación $P$ de $\{1, 2, \dots, N\}$.
Es decir, $P$ es un arreglo de longitud $N$ que contiene cada entero desde $1$ hasta $N$ exactamente una vez.
Puedes realizar la siguiente operación sobre él:
- Elegir un índice $i$ ($1 < i < |P|$).
- Asignar $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Eliminar $P_{i-1}$ y $P_{i+1}$ de $P$. Los elementos restantes se vuelven a indexar comenzando desde $1$.
Cada una de estas operaciones reduce la longitud de $P$ en $2$. En particular, si la longitud de $P$ es $1$ o $2$, esta operación no se puede aplicar.
Halla el número de arreglos distintos que se pueden alcanzar realizando esta operación cero o más veces comenzando desde $P$.
Como este valor puede ser grande, solo necesitas hallarlo módulo $998\,244\,353$.
Entrada
La entrada se proporciona en el siguiente formato:
T N P_1 P_2 ... P_N ...
Restricciones
- Todos los valores de entrada son enteros.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ para todo $i \ne j$.
- Se garantiza que la suma de $N^2$ en todos los casos de prueba no supera $5000^2$.
Salida
Para cada caso de prueba, imprime un único entero — el número de arreglos distintos que se pueden alcanzar realizando la operación cero o más veces sobre $P$, módulo $998\,244\,353$.
Ejemplo
Entrada 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
Salida 1
1 2 5 55 365
Nota
Caso de prueba 1: No se puede realizar ninguna operación.
Caso de prueba 2: Hay dos posibilidades:
- No realizar ninguna operación. El arreglo final es $[2, 1, 3]$.
- Realizar una operación con $i = 2$. El arreglo final es $[3]$.
Estos son los únicos arreglos alcanzables.