I KMP-algoritmen är next-arrayen (även känd som LPS-arrayen, för Longest Prefix Suffix, eller felfunktionen) ett centralt begrepp. Givet en sträng $S = s_1s_2\dots s_n$ av längd $n$, definieras dess next-array $next[1..n]$ så att $next[i]$ representerar längden på det längsta lika äkta prefixet och äkta suffixet av delsträngen $S[1..i]$, specifikt $next[1] = 0$. Formellt definieras den som:

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

Här definieras $S[l..r]$ som delsträngen som bildas av det $l$-te tecknet till det $r$-te tecknet i strängen $S$. Det anses att $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$, vilka båda är tomma strängar.

Givet en array $A[1..n]$ av längd $n$. Du ska räkna hur många olika strängar $S$ av längd $n$ definierade över teckenmängden $\Sigma$ som har en next-array som är exakt lika med den givna arrayen $A$. Storleken på teckenmängden är $m$. Skriv ut antalet sådana strängar modulo $998\,244\,353$.

Indata

Det finns flera testfall i en enda testfil. Den första raden i indatan innehåller ett enda heltal $T$ ($1 \le T \le 10^5$), vilket anger antalet testfall.

För varje testfall:

• Den första raden innehåller två heltal $n$ ($2 \le n \le 10^5$) och $m$ ($1 \le m \le 10^6$) som representerar längden på den givna arrayen och storleken på teckenmängden.
• Den andra raden innehåller $n$ heltal, separerade med mellanslag, som representerar den givna arrayen $A$. Det garanteras att $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$.

Det garanteras att den totala summan av $n$ inte överstiger $5 \times 10^5$, dvs. $\sum n \le 5 \times 10^5$.

Utdata

För varje testfall, skriv ut en enda rad med ett enda heltal som representerar antalet strängar som uppfyller villkoren, med svaret taget modulo $998\,244\,353$.

Exempel

Indata

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

Utdata

3
24
0

Notering

För den andra gruppen av data i exemplet, låt oss anta att teckenmängden är $\Sigma = \{'a', 'b', 'c'\}$. De $24$ strängarna som uppfyller kraven är:

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