W algorytmie KMP tablica next (znana również jako tablica LPS, od Longest Prefix Suffix, lub funkcja prefiksowa) jest kluczowym pojęciem. Dla danego napisu $S = s_1s_2\dots s_n$ o długości $n$, jego tablica next $next[1..n]$ jest zdefiniowana tak, że $next[i]$ oznacza długość najdłuższego wspólnego właściwego prefiksu i właściwego sufiksu podsłowa $S[1..i]$, w szczególności $next[1] = 0$. Formalnie definiuje się ją następująco:

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

Tutaj $S[l..r]$ oznacza podsłowo utworzone od $l$-tego znaku do $r$-tego znaku napisu $S$. Przyjmujemy, że $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$ i oba te napisy są puste.

Dana jest tablica $A[1..n]$ o długości $n$. Musisz policzyć, ile różnych napisów $S$ o długości $n$ nad alfabetem $\Sigma$ ma tablicę next dokładnie równą danej tablicy $A$. Rozmiar alfabetu wynosi $m$. Wypisz liczbę takich napisów modulo $998\,244\,353$.

Wejście

W pojedynczym pliku testowym znajduje się wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 10^5$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

• Pierwszy wiersz zawiera dwie liczby całkowite $n$ ($2 \le n \le 10^5$) oraz $m$ ($1 \le m \le 10^6$), oznaczające odpowiednio długość danej tablicy oraz rozmiar alfabetu.
• Drugi wiersz zawiera $n$ liczb całkowitych oddzielonych spacjami, reprezentujących daną tablicę $A$. Gwarantowane jest, że $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$.

Gwarantowane jest, że łączna suma $n$ nie przekracza $5 \times 10^5$, tzn. $\sum n \le 5 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz pojedynczy wiersz z jedną liczbą całkowitą, oznaczającą liczbę napisów spełniających warunki, modulo $998\,244\,353$.

Przykład

Wejście

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

Wyjście

3
24
0

Uwaga

Dla drugiego zestawu danych z przykładu załóżmy, że alfabet to $\Sigma = \{'a', 'b', 'c'\}$. $24$ napisy spełniające wymagania to:

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