Yana, Mino, White og Huzz eru bestu vinir.
Eftir að hafa loksins lokið krefjandi verkefnum þjálfarans hafði Huzz unnið sér inn hvíld. Hann fann hana á lötum síðdegi, þar sem heimurinn virtist hægja á sér niður í skrið, vafinn í hlýja, gyllta móðu yfirvofandi rökkurs. Ljúfur gola gerði lítið annað en að hræra í rykkornunum sem dönsuðu í sólargeislunum sem féllu á ská í gegnum laufblöð stórrar eikar.
Í þessari syfjuðu og þægilegu kyrrð fann Huzz umröðun í mjúka hákarlaleikfanginu sínu. Hann ákvað að deila henni með vinum sínum til gamans.
Mino elskar að skipta. Hann getur skipt þessari umröðun í nokkur samfelld bil.
Yana elskar að víxla. Hann getur valið eitt samfellt bil og víxlað stærsta og minnsta staki þess.
Nánar tiltekið geta þau framkvæmt eftirfarandi tvær gerðir aðgerða hversu oft sem er, í hvaða röð sem er:
- split: Veldu eitt samfellt bil sem hefur lengd stærri en $1$. Veldu síðan staðsetningu inni í því og skiptu því í tvö aðliggjandi samfelld bil. Til dæmis má skipta $(a_i, \dots, a_j)$ í $(a_i, \dots, a_k)$ og $(a_{k+1}, \dots, a_j)$, þar sem $i \le k < j$.
- swap: Veldu eitt samfellt bil og víxlaðu stærsta og minnsta staki þess.
Eftir að hafa framkvæmt einhvern fjölda aðgerða hætta þau, og öll bilin sem urðu til eru sameinuð í upphaflegri röð sinni til að mynda nýja umröðun.
White elskar að telja. Hún veltir fyrir sér — hversu margar ólíkar umraðanir geta þau fengið?
Þar sem niðurstaðan getur verið mjög stór þarftu aðeins að finna svarið módulo $998\,244\,353$.
Inntak
Fyrsta lína inntaksins inniheldur heiltölu $n$ ($1 \le n \le 500$), lengd umröðunarinnar.
Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), sem tákna umröðunina sjálfa. Tryggt er að $\{a_n\}$ sé umröðun.
Úttak
Prentaðu heiltölu, fjölda ólíkra umraðana sem þau geta fengið módulo $998\,244\,353$.
Dæmi
Inntak
4 1 4 2 3
Úttak
10
Inntak
7 5 1 4 2 6 3 7
Úttak
340
Athugasemd
Í fyrra dæminu eru eftirfarandi allar mögulegar umraðanir sem þau geta fengið:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$