Ti viene data una permutazione $P$ di $\{1, 2, \dots, N\}$.
Cioè, $P$ è un array di lunghezza $N$ contenente ogni numero intero da $1$ a $N$ esattamente una volta.
Puoi eseguire la seguente operazione su di esso:
- Scegli un indice $i$ ($1 < i < |P|$).
- Imposta $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Elimina $P_{i-1}$ e $P_{i+1}$ da $P$. Gli elementi rimanenti vengono quindi reindicizzati a partire da $1$.
Ogni operazione di questo tipo riduce la lunghezza di $P$ di $2$. In particolare, se la lunghezza di $P$ è $1$ o $2$, questa operazione non può essere applicata.
Trova il numero di array distinti che possono essere raggiunti eseguendo questa operazione zero o più volte a partire da $P$.
Poiché questo valore potrebbe essere grande, devi solo trovarlo modulo $998\,244\,353$.
Input
L'input è fornito nel seguente formato:
T N P_1 P_2 ... P_N ...
Vincoli
- Tutti i valori di input sono numeri interi.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ per tutti gli $i \ne j$.
- È garantito che la somma di $N^2$ su tutti i casi di test non supera $5000^2$.
Output
Per ogni caso di test, stampa un singolo numero intero — il numero di array distinti che possono essere raggiunti eseguendo l'operazione zero o più volte su $P$, modulo $998\,244\,353$.
Esempio
Input 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
Output 1
1 2 5 55 365
Note
Caso di test 1: Non è possibile eseguire alcuna operazione.
Caso di test 2: Ci sono due possibilità:
- Non eseguire alcuna operazione. L'array finale è $[2, 1, 3]$.
- Eseguire un'operazione con $i = 2$. L'array finale è $[3]$.
Questi sono gli unici array raggiungibili.