Dana jest permutacja $P$ zbioru $\{1, 2, \dots, N\}$.
Oznacza to, że $P$ jest tablicą o długości $N$, zawierającą każdą liczbę całkowitą od $1$ do $N$ dokładnie raz.
Możesz wykonać na niej następującą operację:
- Wybierz indeks $i$ ($1 < i < |P|$).
- Ustaw $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Usuń $P_{i-1}$ oraz $P_{i+1}$ z $P$. Pozostałe elementy są następnie przeindeksowywane tak, aby ich indeksy zaczynały się od $1$.
Każda taka operacja zmniejsza długość $P$ o $2$. W szczególności, jeśli długość $P$ wynosi $1$ lub $2$, operacji tej nie można zastosować.
Wyznacz liczbę różnych tablic, które można uzyskać, wykonując tę operację zero lub więcej razy, zaczynając od $P$.
Ponieważ wartość ta może być duża, wystarczy znaleźć ją modulo $998\,244\,353$.
Wejście
Wejście podane jest w następującym formacie:
T N P_1 P_2 ... P_N ...
Ograniczenia
- Wszystkie wartości wejściowe są liczbami całkowitymi.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ dla wszystkich $i \ne j$.
- Gwarantuje się, że suma $N^2$ po wszystkich przypadkach testowych nie przekracza $5000^2$.
Wyjście
Dla każdego przypadku testowego wypisz jedną liczbę całkowitą — liczbę różnych tablic, które można uzyskać, wykonując operację zero lub więcej razy na $P$, modulo $998\,244\,353$.
Przykład
Wejście 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
Wyjście 1
1 2 5 55 365
Uwaga
Przypadek testowy 1: Nie można wykonać żadnej operacji.
Przypadek testowy 2: Są dwie możliwości:
- Nie wykonuj żadnych operacji. Końcowa tablica to $[2, 1, 3]$.
- Wykonaj jedną operację dla $i = 2$. Końcowa tablica to $[3]$.
Są to jedyne osiągalne tablice.