Du får oppgitt en permutasjon $P$ av $\{1, 2, \dots, N\}$.
Det vil si at $P$ er en tabell med lengde $N$ som inneholder hvert heltall fra $1$ til $N$ nøyaktig én gang.
Du kan utføre følgende operasjon på den:
- Velg en indeks $i$ ($1 < i < |P|$).
- Sett $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Slett $P_{i-1}$ og $P_{i+1}$ fra $P$. De gjenværende elementene blir deretter omindeksert til å starte fra $1$.
Hver slik operasjon reduserer lengden på $P$ med $2$. Spesielt, hvis lengden på $P$ er $1$ eller $2$, kan ikke denne operasjonen brukes.
Finn antallet forskjellige tabeller som kan nås ved å utføre denne operasjonen null eller flere ganger med start fra $P$.
Siden denne verdien kan være stor, trenger du bare å finne den modulo $998\,244\,353$.
Inndata
Inndataene gis i følgende format:
T N P_1 P_2 ... P_N ...
Begrensninger
- Alle inndataverdier er heltall.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ for alle $i \ne j$.
- Det er garantert at summen av $N^2$ over alle testtilfeller ikke overstiger $5000^2$.
Utdata
For hvert testtilfelle, skriv ut et enkelt heltall — antallet forskjellige tabeller som kan nås ved å utføre operasjonen null eller flere ganger på $P$, modulo $998\,244\,353$.
Eksempel
Inndata 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
Utdata 1
1 2 5 55 365
Merk
Testtilfelle 1: Ingen operasjoner kan utføres.
Testtilfelle 2: Det er to muligheter:
- Utfør ingen operasjoner. Den endelige tabellen er $[2, 1, 3]$.
- Utfør én operasjon med $i = 2$. Den endelige tabellen er $[3]$.
Dette er de eneste tabellene som kan nås.