Im KMP-Algorithmus ist das next-Array (auch bekannt als LPS-Array für Longest Prefix Suffix oder als Fehlerfunktion) ein zentrales Konzept. Gegeben eine Zeichenkette $S = s_1s_2\dots s_n$ der Länge $n$, ist ihr next-Array $next[1..n]$ so definiert, dass $next[i]$ die Länge des längsten übereinstimmenden echten Präfixes und echten Suffixes der Teilzeichenkette $S[1..i]$ darstellt; insbesondere gilt $next[1] = 0$. Formal ist es definiert als:

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

Hierbei ist $S[l..r]$ definiert als die Teilzeichenkette, die vom $l$-ten Zeichen bis zum $r$-ten Zeichen der Zeichenkette $S$ gebildet wird. Es gilt für $\forall 1 \le i \le n$, dass $S[1\dots 0] = S[i+1\dots i]$ beide leere Zeichenketten sind.

Gegeben ist ein Array $A[1..n]$ der Länge $n$. Du musst zählen, wie viele verschiedene Zeichenketten $S$ der Länge $n$ über dem Alphabet $\Sigma$ ein next-Array besitzen, das genau mit dem gegebenen Array $A$ übereinstimmt. Die Größe des Alphabets beträgt $m$. Gib die Anzahl solcher Zeichenketten modulo $998\,244\,353$ aus.

Eingabe

Es gibt mehrere Testfälle in einer einzigen Testdatei. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 10^5$), die die Anzahl der Testfälle angibt.

Für jeden Testfall:

• Die erste Zeile enthält zwei ganze Zahlen $n$ ($2 \le n \le 10^5$) und $m$ ($1 \le m \le 10^6$), die die Länge des gegebenen Arrays und die Größe des Alphabets darstellen.
• Die zweite Zeile enthält $n$ durch Leerzeichen getrennte ganze Zahlen, die das gegebene Array $A$ darstellen. Es wird garantiert, dass $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$ gilt.

Es wird garantiert, dass die Gesamtsumme von $n$ den Wert $5 \times 10^5$ nicht überschreitet, d. h. $\sum n \le 5 \times 10^5$.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer einzelnen ganzen Zahl aus, die die Anzahl der Zeichenketten darstellt, welche die Bedingungen erfüllen, modulo $998\,244\,353$.

Beispiel

Eingabe

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

Ausgabe

3
24
0

Hinweis

Nehmen wir für den zweiten Testfall im Beispiel an, dass das Alphabet $\Sigma = \{'a', 'b', 'c'\}$ ist. Die $24$ Zeichenketten, die die Anforderungen erfüllen, lauten:

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