Sinulle annetaan joukon $\{1, 2, \dots, N\}$ permutaatio $P$.
Toisin sanoen $P$ on pituuden $N$ taulukko, joka sisältää jokaisen kokonaisluvun väliltä $1$ – $N$ täsmälleen kerran.
Voit suorittaa sille seuraavan operaation:
- Valitse indeksi $i$ ($1 < i < |P|$).
- Aseta $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Poista $P_{i-1}$ ja $P_{i+1}$ taulukosta $P$. Jäljelle jäävät alkiot indeksoidaan sen jälkeen uudelleen alkaen luvusta $1$.
Jokainen tällainen operaatio vähentää taulukon $P$ pituutta luvulla $2$. Erityisesti, jos taulukon $P$ pituus on $1$ tai $2$, tätä operaatiota ei voida käyttää.
Etsi erilaisten taulukoiden lukumäärä, jotka voidaan saavuttaa suorittamalla tämä operaatio nolla kertaa tai useammin lähtien taulukosta $P$.
Koska tämä arvo voi olla suuri, sinun tarvitsee vain laskea se modulo $998\,244\,353$.
Syöte
Syöte annetaan seuraavassa muodossa:
T N P_1 P_2 ... P_N ...
Rajoitukset
- Kaikki syötearvot ovat kokonaislukuja.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ kaikilla $i \ne j$.
- On taattu, että arvojen $N^2$ summa yli kaikkien testitapausten ei ylitä arvoa $5000^2$.
Tuloste
Tulosta jokaista testitapausta kohden yksi kokonaisluku — erilaisten taulukoiden lukumäärä, jotka voidaan saavuttaa suorittamalla operaatio nolla kertaa tai useammin taulukolle $P$, modulo $998\,244\,353$.
Esimerkki
Syöte 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
Tuloste 1
1 2 5 55 365
Huomautus
Testitapaus 1: Operaatioita ei voida suorittaa lainkaan.
Testitapaus 2: Mahdollisuuksia on kaksi:
- Älä suorita yhtään operaatiota. Lopullinen taulukko on $[2, 1, 3]$.
- Suorita yksi operaatio arvolla $i = 2$. Lopullinen taulukko on $[3]$.
Nämä ovat ainoat saavutettavissa olevat taulukot.