I KMP-algoritmen er next-arrayen (også kjent som LPS-arrayen, for Longest Prefix Suffix, eller feilfunksjonen) et sentralt begrep. Gitt en streng $S = s_1s_2\dots s_n$ med lengde $n$, er dens next-array $next[1..n]$ definert slik at $next[i]$ representerer lengden på det lengste like ekte prefikset og ekte suffikset til delstrengen $S[1..i]$, spesifikt $next[1] = 0$. Formelt er den definert som:

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

Her er $S[l..r]$ definert som delstrengen dannet av det $l$-te tegnet til det $r$-te tegnet i strengen $S$. Det regnes med at $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$, som begge er tomme strenger.

Gitt en array $A[1..n]$ med lengde $n$. Du må telle hvor mange forskjellige strenger $S$ med lengde $n$ definert over tegnsettet $\Sigma$ som har en next-array som er nøyaktig lik den gitte arrayen $A$. Størrelsen på tegnsettet er $m$. Skriv ut antallet slike strenger modulo $998\,244\,353$.

Inndata

Det er flere testtilfeller i én enkelt testfil. Den første linjen i inndataene inneholder ett enkelt heltall $T$ ($1 \le T \le 10^5$), som angir antallet testtilfeller.

For hvert testtilfelle:

• Den første linjen inneholder to heltall $n$ ($2 \le n \le 10^5$) og $m$ ($1 \le m \le 10^6$) som representerer lengden på den gitte arrayen og størrelsen på tegnsettet.
• Den andre linjen inneholder $n$ heltall,atskilt med mellomrom, som representerer den gitte arrayen $A$. Det er garantert at $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$.

Det er garantert at den totale summen av $n$ ikke overstiger $5 \times 10^5$, dvs. $\sum n \le 5 \times 10^5$.

Utdata

For hvert testtilfelle, skriv ut én enkelt linje med ett enkelt heltall som representerer antallet strenger som oppfyller betingelsene, med svaret tatt modulo $998\,244\,353$.

Eksempel

Inndata

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

Merk

For den andre gruppen med data i eksempelet, la oss anta at tegnsettet er $\Sigma = \{'a', 'b', 'c'\}$. De $24$ strengene som oppfyller kravene er:

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