Du får en permutation $P$ av $\{1, 2, \dots, N\}$.
Det vill säga, $P$ är en array med längden $N$ som innehåller varje heltal från $1$ till $N$ exakt en gång.
Du kan utföra följande operation på den:
- Välj ett index $i$ ($1 < i < |P|$).
- Sätt $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Ta bort $P_{i-1}$ och $P_{i+1}$ från $P$. De återstående elementen omindexeras sedan så att de börjar från $1$.
Varje sådan operation minskar längden på $P$ med $2$. I synnerhet, om längden på $P$ är $1$ eller $2$, kan denna operation inte tillämpas.
Hitta antalet distinkta arrayer som kan nås genom att utföra denna operation noll eller flera gånger med start från $P$.
Eftersom detta värde kan vara stort behöver du bara hitta det modulo $998\,244\,353$.
Indata
Indata ges i följande format:
T N P_1 P_2 ... P_N ...
Begränsningar
- Alla indatavärden är heltal.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ för alla $i \ne j$.
- Det garanteras att summan av $N^2$ över alla testfall inte överstiger $5000^2$.
Utdata
För varje testfall, skriv ut ett enda heltal — antalet distinkta arrayer som kan nås genom att utföra operationen noll eller flera gånger på $P$, modulo $998\,244\,353$.
Exempel
Indata 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
Förklaring
Testfall 1: Inga operationer kan utföras.
Testfall 2: Det finns två möjligheter:
- Utför inga operationer. Den slutliga arrayen är $[2, 1, 3]$.
- Utför en operation med $i = 2$. Den slutliga arrayen är $[3]$.
Dessa är de enda nåbara arrayerna.