On vous donne une permutation $P$ de $\{1, 2, \dots, N\}$.
Autrement dit, $P$ est un tableau de longueur $N$ contenant chaque entier de $1$ à $N$ exactement une fois.
Vous pouvez effectuer l'opération suivante sur ce tableau :
- Choisir un indice $i$ ($1 < i < |P|$).
- Affecter $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Supprimer $P_{i-1}$ et $P_{i+1}$ de $P$. Les éléments restants sont ensuite réindexés à partir de $1$.
Chaque opération de ce type réduit la longueur de $P$ de $2$. En particulier, si la longueur de $P$ est $1$ ou $2$, cette opération ne peut pas être appliquée.
Trouvez le nombre de tableaux distincts qui peuvent être atteints en effectuant cette opération zéro ou plusieurs fois en partant de $P$.
Comme cette valeur peut être grande, vous devez seulement la calculer modulo $998\,244\,353$.
Entrée
L'entrée est donnée dans le format suivant :
T N P_1 P_2 ... P_N ...
Contraintes
- Toutes les valeurs d'entrée sont des entiers.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ pour tous $i \ne j$.
- Il est garanti que la somme de $N^2$ sur l'ensemble des cas de test ne dépasse pas $5000^2$.
Sortie
Pour chaque cas de test, affichez un seul entier — le nombre de tableaux distincts pouvant être atteints en effectuant l'opération zéro ou plusieurs fois sur $P$, modulo $998\,244\,353$.
Exemple
Entrée 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
Sortie 1
1 2 5 55 365
Note
Cas de test 1 : Aucune opération ne peut être effectuée.
Cas de test 2 : Il y a deux possibilités :
- N'effectuer aucune opération. Le tableau final est $[2, 1, 3]$.
- Effectuer une opération avec $i = 2$. Le tableau final est $[3]$.
Ce sont les seuls tableaux atteignables.