En el algoritmo KMP, el arreglo next (también conocido como arreglo LPS, por Longest Prefix Suffix, o función de fallo) es un concepto fundamental. Dada una cadena $S = s_1s_2\dots s_n$ de longitud $n$, su arreglo next $next[1..n]$ se define de modo que $next[i]$ representa la longitud del prefijo propio y sufijo propio iguales más largos de la subcadena $S[1..i]$, específicamente, $next[1] = 0$. Formalmente, se define como:

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

Aquí, $S[l..r]$ se define como la subcadena formada desde el $l$-ésimo carácter hasta el $r$-ésimo carácter de la cadena $S$. Se considera que $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$, siendo ambas cadenas vacías.

Dado un arreglo $A[1..n]$ de longitud $n$, debes contar cuántas cadenas diferentes $S$ de longitud $n$ definidas sobre el conjunto de caracteres $\Sigma$ tienen un arreglo next que es exactamente igual al arreglo dado $A$. El tamaño del conjunto de caracteres es $m$. Imprime el número de tales cadenas módulo $998\,244\,353$.

Entrada

Hay múltiples casos de prueba en un solo archivo de prueba. La primera línea de la entrada contiene un solo entero $T$ ($1 \le T \le 10^5$), que indica el número de casos de prueba.

Para cada caso de prueba:

• La primera línea contiene dos enteros $n$ ($2 \le n \le 10^5$) y $m$ ($1 \le m \le 10^6$) que representan la longitud del arreglo dado y el tamaño del conjunto de caracteres.
• La segunda línea contiene $n$ enteros separados por espacios, que representan el arreglo dado $A$. Se garantiza que $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$.

Se garantiza que la suma total de $n$ no supera $5 \times 10^5$, es decir, $\sum n \le 5 \times 10^5$.

Salida

Para cada caso de prueba, imprime una sola línea con un solo entero, que represente el número de cadenas que satisfacen las condiciones, tomando la respuesta módulo $998\,244\,353$.

Ejemplo

Entrada

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

Salida

3
24
0

Nota

Para el segundo grupo de datos del ejemplo, supongamos que el conjunto de caracteres es $\Sigma = \{'a', 'b', 'c'\}$. Las $24$ cadenas que cumplen los requisitos son:

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