Í KMP-reikniritinu er next-fylkið (einnig þekkt sem LPS-fylkið, fyrir Longest Prefix Suffix, eða bilunarfallið) grunn- hugtak. Gefinn er strengur $S = s_1s_2\dots s_n$ af lengd $n$, og er next-fylki hans $next[1..n]$ skilgreint þannig að $next[i]$ táknar lengd lengsta eins eiginlega forskeytis og eiginlega viðskeytis hlutstrengsins $S[1..i]$, nánar tiltekið er $next[1] = 0$. Formlega er það skilgreint sem:

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

Hér er $S[l..r]$ skilgreint sem hlutstrengurinn sem myndast af $l$-ta stafnum til $r$-ta stafsins í strengnum $S$. Litið er svo á að $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$, sem eru báðir tómir strengir.

Gefið er fylki $A[1..n]$ af lengd $n$. Þú þarft að telja hversu margir ólíkir strengir $S$ af lengd $n$ skilgreindir yfir stafamenginu $\Sigma$ hafa next-fylki sem er nákvæmlega jafnt gefna fylkinu $A$. Stærð stafamengisins er $m$. Skrifið út fjölda slíkra strengja módúló $998\,244\,353$.

Inntak

Það eru margir prófunartilvik í einni prófunarskrá. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T \le 10^5$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik:

• Fyrsta línan inniheldur tvær heiltölur $n$ ($2 \le n \le 10^5$) og $m$ ($1 \le m \le 10^6$) sem tákna lengd gefna fylkisins og stærð stafamengisins.
• Önnur línan inniheldur $n$ heiltölur, aðskildar með bilum, sem tákna gefna fylkið $A$. Tryggt er að $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$.

Tryggt er að heildarsumma $n$ fari ekki yfir $5 \times 10^5$, þ.e. $\sum n \le 5 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal skrifa út eina línu með einni heiltölu, sem táknar fjölda strengja sem uppfylla skilyrðin, tekið módúló $998\,244\,353$.

Dæmi

Inntak

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

Úttak

3
24
0

Athugasemd

Fyrir annan gagnahópinn í dæminu skulum við gera ráð fyrir að stafamengið sé $\Sigma = \{'a', 'b', 'c'\}$. Strengirnir $24$ sem uppfylla kröfurnar eru:

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