Yana, Mino, White ja Huzz ovat parhaita ystäviä.
Saatuaan vihdoin valmiiksi valmentajan vaativat tehtävät Huzz oli ansainnut lepohetken. Hän löysi sen eräänä laiskana iltapäivänä, jolloin maailma tuntui hidastuvan mateluksi lähestyvän iltahämärän lämpimän kultaisen utuverhon sisällä. Lempeä tuulenvire tuskin teki muuta kuin liikutti pölyhiukkasia, jotka tanssivat suuren tammen lehtien lomasta viistosti siivilöityvissä auringonsäteissä.
Tuossa uneliaassa ja mukavassa tyhjyydessä Huzz löysi permutaation pehmeästä hailelustaan. Hän päätti jakaa sen ystäviensä kanssa huvin vuoksi.
Mino rakastaa jakamista. Hän voi jakaa tämän permutaation useiksi yhtenäisiksi väleiksi.
Yana rakastaa vaihtamista. Hän voi valita yhden yhtenäisen välin ja vaihtaa keskenään sen suurimman ja pienimmän alkion.
Tarkemmin sanottuna he voivat suorittaa seuraavia kahta operaatiotyyppiä mielivaltaisen monta kertaa, missä tahansa järjestyksessä:
- split: Valitse yksi yhtenäinen väli, jonka pituus on suurempi kuin $1$. Valitse sitten sen sisältä kohta ja jaa se kahdeksi vierekkäiseksi yhtenäiseksi väliksi. Esimerkiksi $(a_i, \dots, a_j)$ voidaan jakaa väleiksi $(a_i, \dots, a_k)$ ja $(a_{k+1}, \dots, a_j)$, missä $i \le k < j$.
- swap: Valitse yksi yhtenäinen väli ja vaihda keskenään sen suurin ja pienin alkio.
Suoritettuaan haluamansa määrän operaatioita he lopettavat, ja kaikki syntyneet välit yhdistetään alkuperäisessä järjestyksessään uudeksi permutaatioksi.
White rakastaa laskemista. Hän pohtii — kuinka monta eri permutaatiota he voivat saada?
Koska tulos voi olla hyvin suuri, sinun tarvitsee vain etsiä vastaus modulo $998\,244\,353$.
Syöte
Syötteen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 500$), permutaation pituuden.
Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), jotka kuvaavat itse permutaatiota. On taattu, että $\{a_n\}$ on permutaatio.
Tuloste
Tulosta kokonaisluku, heidän saamiensa erilaisten permutaatioiden lukumäärä modulo $998\,244\,353$.
Esimerkit
Syöte
4 1 4 2 3
Tuloste
10
Syöte
7 5 1 4 2 6 3 7
Tuloste
340
Huomautus
Ensimmäisessä esimerkissä seuraavat ovat kaikki mahdolliset permutaatiot, jotka he voivat saada:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$