Yana, Mino, White und Huzz sind beste Freunde.

Nachdem Huzz endlich die anspruchsvollen Aufgaben des Trainers erledigt hatte, hatte er sich eine Pause verdient. Er fand sie an einem trägen Nachmittag, an dem die Welt im Schneckentempo zu vergehen schien, gehüllt in den warmen, goldenen Dunst der nahenden Abenddämmerung. Eine sanfte Brise tat kaum mehr, als die Staubkörnchen aufzuwirbeln, die in den schräg durch das Laub einer großen Eiche fallenden Sonnenstrahlen tanzten.

In dieser schläfrigen, behaglichen Leere fand Huzz eine Permutation in seinem weichen Plüschhai. Er beschloss, sie zum Spaß mit seinen Freunden zu teilen.

Mino liebt das Aufteilen. Er kann diese Permutation in mehrere zusammenhängende Segmente aufteilen.

Yana liebt das Vertauschen. Er kann ein zusammenhängendes Segment auswählen und dessen größtes und kleinstes Element vertauschen.

Genauer gesagt können sie die folgenden beiden Arten von Operationen beliebig oft und in beliebiger Reihenfolge ausführen:

• split: Wähle ein zusammenhängendes Segment, dessen Länge größer als $1$ ist. Wähle dann eine Position darin und teile es in zwei benachbarte zusammenhängende Segmente auf. Zum Beispiel kann $(a_i, \dots, a_j)$ in $(a_i, \dots, a_k)$ und $(a_{k+1}, \dots, a_j)$ aufgeteilt werden, wobei $i \le k < j$ gilt.
• swap: Wähle ein zusammenhängendes Segment und vertausche sein größtes und sein kleinstes Element.

Nachdem sie beliebig viele Operationen ausgeführt haben, hören sie auf, und alle entstandenen Segmente werden in ihrer ursprünglichen Reihenfolge zusammengefügt, um eine neue Permutation zu bilden.

White liebt das Zählen. Sie fragt sich — wie viele verschiedene Permutationen können sie erhalten?

Da das Ergebnis sehr groß sein kann, musst du die Antwort nur modulo $998\,244\,353$ bestimmen.

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl $n$ ($1 \le n \le 500$), die Länge der Permutation.

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), welche die Permutation selbst darstellen. Es wird garantiert, dass $\{a_n\}$ eine Permutation ist.

Ausgabe

Gib eine ganze Zahl aus, die Anzahl der verschiedenen Permutationen, die sie erhalten können, modulo $998\,244\,353$.

Beispiele

Eingabe

4
1 4 2 3

Ausgabe

10

Eingabe

7
5 1 4 2 6 3 7

Ausgabe

340

Hinweis

Im ersten Beispiel sind im Folgenden alle möglichen Permutationen aufgeführt, die sie erhalten können:

$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$