Yana, Mino, White, dan Huzz adalah sahabat karib.
Setelah akhirnya menyelesaikan tugas-tugas berat dari pelatih, Huzz mendapatkan waktu istirahat. Ia menemukannya pada suatu sore yang santai, ketika dunia terasa melambat, diselimuti kabut keemasan yang hangat menjelang senja. Angin sepoi-sepoi hanya sedikit menggerakkan butiran debu yang menari di berkas sinar matahari yang menembus dedaunan pohon ek besar.
Di dalam kehampaan yang nyaman dan membuat mengantuk itu, Huzz menemukan sebuah permutasi di dalam boneka hiu lembutnya. Ia memutuskan untuk membagikannya kepada teman-temannya untuk bersenang-senang.
Mino suka membelah. Ia dapat membelah permutasi ini menjadi beberapa segmen berurutan.
Yana suka menukar. Ia dapat memilih satu segmen berurutan dan menukar elemen maksimum serta minimumnya.
Secara spesifik, mereka dapat melakukan dua jenis operasi berikut berapa kali pun, dalam urutan apa pun:
- split: Pilih satu segmen berurutan yang panjangnya lebih dari $1$. Kemudian pilih sebuah posisi di dalamnya dan belah menjadi dua segmen berurutan yang bersebelahan. Misalnya, $(a_i, \dots, a_j)$ dapat dibelah menjadi $(a_i, \dots, a_k)$ dan $(a_{k+1}, \dots, a_j)$, di mana $i \le k < j$.
- swap: Pilih satu segmen berurutan dan tukar elemen maksimum serta minimumnya.
Setelah melakukan sejumlah operasi, mereka berhenti, dan semua segmen yang dihasilkan digabungkan kembali sesuai urutan aslinya untuk membentuk sebuah permutasi baru.
White suka menghitung. Ia bertanya-tanya — berapa banyak permutasi berbeda yang dapat mereka peroleh?
Karena hasilnya bisa sangat besar, Anda hanya perlu mencari jawabannya modulo $998\,244\,353$.
Masukan
Baris pertama masukan berisi sebuah bilangan bulat $n$ ($1 \le n \le 500$), yaitu panjang permutasi.
Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), yang menyatakan permutasi itu sendiri. Dijamin bahwa $\{a_n\}$ adalah sebuah permutasi.
Keluaran
Cetak sebuah bilangan bulat, yaitu banyaknya permutasi berbeda yang dapat mereka peroleh modulo $998\,244\,353$.
Contoh
Masukan
4 1 4 2 3
Keluaran
10
Masukan
7 5 1 4 2 6 3 7
Keluaran
340
Catatan
Pada contoh pertama, berikut adalah semua kemungkinan permutasi yang dapat mereka peroleh:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$