Þér er gefin umröðun $P$ á $\{1, 2, \dots, N\}$.
Það er að segja, $P$ er fylki af lengd $N$ sem inniheldur hverja heiltölu frá $1$ til $N$ nákvæmlega einu sinni.
Þú getur framkvæmt eftirfarandi aðgerð á það:
- Veldu vísi $i$ ($1 < i < |P|$).
- Settu $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Eyddu $P_{i-1}$ og $P_{i+1}$ úr $P$. Stökin sem eftir eru fá síðan nýja vísa sem byrja á $1$.
Hver slík aðgerð minnkar lengd $P$ um $2$. Sér í lagi, ef lengd $P$ er $1$ eða $2$, þá er ekki hægt að beita þessari aðgerð.
Finndu fjölda ólíkra fylkja sem hægt er að ná með því að framkvæma þessa aðgerð núll sinnum eða oftar, byrjandi á $P$.
Þar sem þetta gildi getur verið stórt þarftu aðeins að finna það modulo $998\,244\,353$.
Inntak
Inntakið er gefið á eftirfarandi sniði:
T N P_1 P_2 ... P_N ...
Skorður
- Öll inntaksgildi eru heiltölur.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ fyrir öll $i \ne j$.
- Það er tryggt að summa $N^2$ yfir öll prófunartilvik fari ekki yfir $5000^2$.
Úttak
Fyrir hvert prófunartilvik skaltu prenta eina heiltölu — fjölda ólíkra fylkja sem hægt er að ná með því að framkvæma aðgerðina núll sinnum eða oftar á $P$, modulo $998\,244\,353$.
Dæmi
Inntak 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
Úttak 1
1 2 5 55 365
Athugasemd
Prófunartilvik 1: Engar aðgerðir er hægt að framkvæma.
Prófunartilvik 2: Það eru tveir möguleikar:
- Framkvæma engar aðgerðir. Lokafylkið er $[2, 1, 3]$.
- Framkvæma eina aðgerð með $i = 2$. Lokafylkið er $[3]$.
Þetta eru einu fylkin sem hægt er að ná.