Yana, Mino, White i Huzz są najlepszymi przyjaciółmi.
Ukończywszy wreszcie wymagające zadania trenera, Huzz zasłużył na odpoczynek. Znalazł go w jedno leniwe popołudnie, gdy świat zdawał się zwalniać do żółwiego tempa, spowity w ciepłą, złotą mgiełkę nadchodzącego zmierzchu. Delikatny wietrzyk ledwie poruszał drobinkami kurzu tańczącymi w promieniach słońca wpadających ukośnie przez liście wielkiego dębu.
W tej sennej, przyjemnej pustce Huzz znalazł permutację w swoim miękkim pluszowym rekinie. Postanowił podzielić się nią z przyjaciółmi dla zabawy.
Mino uwielbia dzielenie. Może podzielić tę permutację na kilka spójnych przedziałów.
Yana uwielbia zamianę. Może wybrać jeden spójny przedział i zamienić miejscami jego element największy i najmniejszy.
Dokładniej, mogą oni wykonywać następujące dwa rodzaje operacji dowolną liczbę razy, w dowolnej kolejności:
- split: Wybierz jeden spójny przedział o długości większej niż $1$. Następnie wybierz pozycję wewnątrz niego i podziel go na dwa sąsiadujące spójne przedziały. Na przykład $(a_i, \dots, a_j)$ można podzielić na $(a_i, \dots, a_k)$ oraz $(a_{k+1}, \dots, a_j)$, gdzie $i \le k < j$.
- swap: Wybierz jeden spójny przedział i zamień miejscami jego element największy i najmniejszy.
Po wykonaniu dowolnej liczby operacji kończą oni działanie, a wszystkie powstałe przedziały są łączone w ich pierwotnej kolejności, tworząc nową permutację.
White uwielbia zliczanie. Zastanawia się — ile różnych permutacji mogą oni otrzymać?
Ponieważ wynik może być bardzo duży, wystarczy wyznaczyć odpowiedź modulo $998\,244\,353$.
Wejście
Pierwszy wiersz wejścia zawiera liczbę całkowitą $n$ ($1 \le n \le 500$) — długość permutacji.
Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), reprezentujących samą permutację. Gwarantowane jest, że $\{a_n\}$ jest permutacją.
Wyjście
Wypisz jedną liczbę całkowitą — liczbę różnych permutacji, jakie mogą otrzymać, modulo $998\,244\,353$.
Przykłady
Wejście
4 1 4 2 3
Wyjście
10
Wejście
7 5 1 4 2 6 3 7
Wyjście
340
Uwaga
W pierwszym przykładzie poniżej wypisano wszystkie możliwe permutacje, jakie mogą otrzymać:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$