Yana, Mino, White og Huzz er bestevenner.
Etter endelig å ha fullført trenerens krevende oppgaver, hadde Huzz gjort seg fortjent til en hvil. Han fant den på en lat ettermiddag, der verden syntes å gå i sneglefart, pakket inn i den varme, gylne disen fra den kommende skumringen. En svak bris gjorde knapt mer enn å virvle opp støvkornene som danset i solstrålene som falt skrått gjennom løvet på en stor eik.
I dette søvnige, behagelige tomrommet fant Huzz en permutasjon i det myke haikosedyret sitt. Han bestemte seg for å dele den med vennene sine for moro skyld.
Mino elsker å dele opp. Han kan dele denne permutasjonen inn i flere sammenhengende segmenter.
Yana elsker å bytte om. Han kan velge ett sammenhengende segment og bytte om dets største og minste element.
Mer spesifikt kan de utføre følgende to typer operasjoner hvor mange ganger som helst, i hvilken som helst rekkefølge:
- split: Velg ett sammenhengende segment med lengde større enn $1$. Velg deretter en posisjon inne i det og del det i to tilstøtende sammenhengende segmenter. For eksempel kan $(a_i, \dots, a_j)$ deles inn i $(a_i, \dots, a_k)$ og $(a_{k+1}, \dots, a_j)$, der $i \le k < j$.
- swap: Velg ett sammenhengende segment og bytt om dets største og minste element.
Etter å ha utført et vilkårlig antall operasjoner stopper de, og alle de resulterende segmentene slås sammen i sin opprinnelige rekkefølge for å danne en ny permutasjon.
White elsker å telle. Hun lurer på — hvor mange forskjellige permutasjoner kan de oppnå?
Siden resultatet kan bli svært stort, trenger du bare å finne svaret modulo $998\,244\,353$.
Inndata
Den første linjen i inndataene inneholder et heltall $n$ ($1 \le n \le 500$), lengden på permutasjonen.
Den andre linjen inneholder $n$ heltall $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), som representerer selve permutasjonen. Det garanteres at $\{a_n\}$ er en permutasjon.
Utdata
Skriv ut et heltall, antallet forskjellige permutasjoner de kan oppnå modulo $998\,244\,353$.
Eksempler
Inndata
4 1 4 2 3
Utdata
10
Inndata
7 5 1 4 2 6 3 7
Utdata
340
Forklaring
I det første eksempelet er følgende alle mulige permutasjoner de kan oppnå:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$