Dans l'algorithme KMP, le tableau next (également appelé tableau LPS, pour Longest Prefix Suffix, ou fonction d'échec) est un concept fondamental. Étant donné une chaîne de caractères $S = s_1s_2\dots s_n$ de longueur $n$, son tableau next $next[1..n]$ est défini de telle sorte que $next[i]$ représente la longueur du plus long préfixe propre et suffixe propre égaux de la sous-chaîne $S[1..i]$, avec en particulier $next[1] = 0$. Formellement, il est défini par :

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

Ici, $S[l..r]$ est défini comme la sous-chaîne formée du $l$-ième caractère au $r$-ième caractère de la chaîne $S$. On considère que $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$, qui sont toutes deux des chaînes vides.

On vous donne un tableau $A[1..n]$ de longueur $n$. Vous devez compter combien de chaînes différentes $S$ de longueur $n$ définies sur l'alphabet $\Sigma$ ont un tableau next exactement égal au tableau $A$ donné. La taille de l'alphabet est $m$. Affichez le nombre de telles chaînes modulo $998\,244\,353$.

Entrée

Il y a plusieurs cas de test dans un seul fichier de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T \le 10^5$), indiquant le nombre de cas de test.

Pour chaque cas de test :

• La première ligne contient deux entiers $n$ ($2 \le n \le 10^5$) et $m$ ($1 \le m \le 10^6$) représentant la longueur du tableau donné et la taille de l'alphabet.
• La deuxième ligne contient $n$ entiers séparés par des espaces, représentant le tableau donné $A$. Il est garanti que $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$.

Il est garanti que la somme totale de $n$ ne dépasse pas $5 \times 10^5$, c'est-à-dire $\sum n \le 5 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un seul entier, représentant le nombre de chaînes qui satisfont aux conditions, la réponse étant prise modulo $998\,244\,353$.

Exemple

Entrée

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

Sortie

3
24
0

Note

Pour le deuxième groupe de données de l'exemple, supposons que l'alphabet soit $\Sigma = \{'a', 'b', 'c'\}$. Les $24$ chaînes qui répondent aux exigences sont :

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