Anda diberikan sebuah permutasi $P$ dari $\{1, 2, \dots, N\}$.
Artinya, $P$ adalah sebuah array dengan panjang $N$ yang memuat setiap bilangan bulat dari $1$ hingga $N$ tepat satu kali.
Anda dapat melakukan operasi berikut padanya:
- Pilih sebuah indeks $i$ ($1 < i < |P|$).
- Tetapkan $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Hapus $P_{i-1}$ dan $P_{i+1}$ dari $P$. Elemen-elemen yang tersisa kemudian diberi indeks ulang mulai dari $1$.
Setiap operasi semacam itu mengurangi panjang $P$ sebanyak $2$. Secara khusus, jika panjang $P$ adalah $1$ atau $2$, maka operasi ini tidak dapat diterapkan.
Carilah banyaknya array berbeda yang dapat dicapai dengan melakukan operasi ini nol kali atau lebih dimulai dari $P$.
Karena nilai ini bisa sangat besar, Anda hanya perlu mencarinya dalam modulo $998\,244\,353$.
Masukan
Masukan diberikan dalam format berikut:
T N P_1 P_2 ... P_N ...
Batasan
- Semua nilai masukan adalah bilangan bulat.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ untuk semua $i \ne j$.
- Dijamin bahwa jumlah dari $N^2$ di semua kasus uji tidak melebihi $5000^2$.
Keluaran
Untuk setiap kasus uji, cetak sebuah bilangan bulat — banyaknya array berbeda yang dapat dicapai dengan melakukan operasi tersebut nol kali atau lebih pada $P$, modulo $998\,244\,353$.
Contoh
Masukan 1
5 2 2 1 3 2 1 3 5 3 1 4 5 2 10 1 2 3 4 5 6 7 8 9 10 15 5 7 6 12 2 13 10 1 11 4 3 9 14 15 8
Keluaran 1
1 2 5 55 365
Catatan
Kasus uji 1: Tidak ada operasi yang dapat dilakukan.
Kasus uji 2: Terdapat dua kemungkinan:
- Tidak melakukan operasi apa pun. Array akhirnya adalah $[2, 1, 3]$.
- Lakukan satu operasi dengan $i = 2$. Array akhirnya adalah $[3]$.
Ini adalah satu-satunya array yang dapat dicapai.