KMP-algoritmissa next-taulukko (tunnetaan myös nimellä LPS-taulukko, lyhenne sanoista Longest Prefix Suffix, tai virhefunktio) on keskeinen käsite. Kun annetaan pituutta $n$ oleva merkkijono $S = s_1s_2\dots s_n$, sen next-taulukko $next[1..n]$ määritellään siten, että $next[i]$ kuvaa osamerkkijonon $S[1..i]$ pisimmän yhtä suuren aidon etuliitteen ja aidon jälkiliitteen pituutta; erityisesti $next[1] = 0$. Muodollisesti se määritellään seuraavasti:

$$next[i] = \max_{k=0,\dots,i-1} \{k : S[1\dots k] = S[i-k+1\dots i]\}$$

Tässä $S[l..r]$ määritellään osamerkkijonoksi, joka muodostuu merkkijonon $S$ $l$-nnestä merkistä $r$-nteen merkkiin. Katsotaan, että $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$, jotka molemmat ovat tyhjiä merkkijonoja.

Annetaan pituutta $n$ oleva taulukko $A[1..n]$. Sinun tulee laskea, kuinka monella merkkijoukon $\Sigma$ päälle määritellyllä eri merkkijonolla $S$, jonka pituus on $n$, on next-taulukko, joka on täsmälleen yhtä suuri kuin annettu taulukko $A$. Merkkijoukon koko on $m$. Tulosta tällaisten merkkijonojen lukumäärä modulo $998\,244\,353$.

Syöte

Yhdessä testitiedostossa on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 10^5$), joka ilmoittaa testitapausten lukumäärän.

Jokaiselle testitapaukselle:

• Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ($2 \le n \le 10^5$) ja $m$ ($1 \le m \le 10^6$), jotka kuvaavat annetun taulukon pituutta ja merkkijoukon kokoa.
• Toinen rivi sisältää $n$ välilyönnein eroteltua kokonaislukua, jotka kuvaavat annettua taulukkoa $A$. On taattu, että $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$.

On taattu, että lukujen $n$ kokonaissumma ei ylitä arvoa $5 \times 10^5$, eli $\sum n \le 5 \times 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, jolla on yksi kokonaisluku, joka kuvaa ehdot täyttävien merkkijonojen lukumäärää modulo $998\,244\,353$.

Esimerkki

Syöte

3
3 3
0 1 2
7 3
0 0 0 1 2 3 0
7 3
0 0 0 1 2 3 1

Tuloste

3
24
0

Huomautus

Oletetaan esimerkin toisessa tietoryhmässä, että merkkijoukko on $\Sigma = \{'a', 'b', 'c'\}$. Vaatimukset täyttävät $24$ merkkijonoa ovat:

abbabbb abbabbc abcabcb abcabcc acbacbb acbacbc
accaccb accaccc baabaaa baabaac bacbaca bacbacc
bcabcaa bcabcac bccbcca bccbccc caacaaa caacaab
cabcaba cabcabb cbacbaa cbacbab cbbcbba cbbcbbb