Yana, Mino, White och Huzz är bästa vänner.
Efter att äntligen ha avslutat tränarens krävande uppgifter hade Huzz förtjänat en vila. Han fann den en lat eftermiddag då världen tycktes sakta ner till krypfart, insvept i det varma, gyllene diset från den annalkande skymningen. En mild bris gjorde knappt mer än att röra om dammkornen som dansade i solstrålarna som föll snett genom löven på en stor ek.
I detta sömniga, behagliga tomrum hittade Huzz en permutation i sin mjuka hajleksak. Han bestämde sig för att dela den med sina vänner på skoj.
Mino älskar att dela upp. Han kan dela upp denna permutation i flera sammanhängande segment.
Yana älskar att byta plats. Han kan välja ett sammanhängande segment och byta plats på dess största och minsta element.
Mer specifikt kan de utföra följande två typer av operationer valfritt antal gånger, i valfri ordning:
- split: Välj ett sammanhängande segment vars längd är större än $1$. Välj sedan en position inuti det och dela upp det i två intilliggande sammanhängande segment. Till exempel kan $(a_i, \dots, a_j)$ delas upp i $(a_i, \dots, a_k)$ och $(a_{k+1}, \dots, a_j)$, där $i \le k < j$.
- swap: Välj ett sammanhängande segment och byt plats på dess största och minsta element.
Efter att ha utfört valfritt antal operationer slutar de, och alla resulterande segment slås samman i sin ursprungliga ordning för att bilda en ny permutation.
White älskar att räkna. Hon undrar — hur många olika permutationer kan de erhålla?
Eftersom resultatet kan bli mycket stort behöver du bara hitta svaret modulo $998\,244\,353$.
Indata
Den första raden i indatan innehåller ett heltal $n$ ($1 \le n \le 500$), längden på permutationen.
Den andra raden innehåller $n$ heltal $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), som representerar själva permutationen. Det garanteras att $\{a_n\}$ är en permutation.
Utdata
Skriv ut ett heltal, antalet olika permutationer de kan erhålla modulo $998\,244\,353$.
Exempel
Indata
4 1 4 2 3
Utdata
10
Indata
7 5 1 4 2 6 3 7
Utdata
340
Förklaring
I det första exemplet är följande alla möjliga permutationer de kan erhålla:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$