Dir ist eine Permutation $P$ von $\{1, 2, \dots, N\}$ gegeben.
Das heißt, $P$ ist ein Array der Länge $N$, das jede ganze Zahl von $1$ bis $N$ genau einmal enthält.
Du kannst die folgende Operation darauf ausführen:
- Wähle einen Index $i$ ($1 < i < |P|$).
- Setze $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Lösche $P_{i-1}$ und $P_{i+1}$ aus $P$. Die verbleibenden Elemente werden anschließend neu indiziert, beginnend bei $1$.
Jede solche Operation verringert die Länge von $P$ um $2$. Insbesondere kann diese Operation nicht angewendet werden, wenn die Länge von $P$ gleich $1$ oder $2$ ist.
Bestimme die Anzahl der verschiedenen Arrays, die erreicht werden können, indem diese Operation null- oder mehrmals ausgehend von $P$ ausgeführt wird.
Da dieser Wert groß sein kann, musst du ihn nur modulo $998\,244\,353$ bestimmen.
Eingabe
Die Eingabe erfolgt im folgenden Format:
T N P_1 P_2 ... P_N ...
Einschränkungen
- Alle Eingabewerte sind ganze Zahlen.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ für alle $i \ne j$.
- Es wird garantiert, dass die Summe von $N^2$ über alle Testfälle $5000^2$ nicht überschreitet.
Ausgabe
Gib für jeden Testfall eine einzige ganze Zahl aus — die Anzahl der verschiedenen Arrays, die durch null- oder mehrmaliges Ausführen der Operation auf $P$ erreicht werden können, modulo $998\,244\,353$.
Beispiel
Eingabe 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
Ausgabe 1
1 2 5 55 365
Hinweis
Testfall 1: Es können keine Operationen ausgeführt werden.
Testfall 2: Es gibt zwei Möglichkeiten:
- Keine Operationen ausführen. Das endgültige Array ist $[2, 1, 3]$.
- Eine Operation mit $i = 2$ ausführen. Das endgültige Array ist $[3]$.
Dies sind die einzigen erreichbaren Arrays.