Universal Cup Judging System

Universal Cup

시간 제한: 3.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

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.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.