Dalam algoritma KMP, larik next (juga dikenal sebagai larik LPS, singkatan dari Longest Prefix Suffix, atau fungsi kegagalan) adalah konsep inti. Diberikan sebuah string $S = s_1s_2\dots s_n$ dengan panjang $n$, larik next-nya $next[1..n]$ didefinisikan sedemikian sehingga $next[i]$ menyatakan panjang prefiks sejati dan sufiks sejati terpanjang yang sama dari substring $S[1..i]$, secara khusus, $next[1] = 0$. Secara formal, ini didefinisikan sebagai:

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

Di sini, $S[l..r]$ didefinisikan sebagai substring yang dibentuk oleh karakter ke-$l$ hingga karakter ke-$r$ dari string $S$. Dianggap bahwa $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$, yang keduanya merupakan string kosong.

Diberikan sebuah larik $A[1..n]$ dengan panjang $n$. Anda perlu menghitung berapa banyak string $S$ berbeda dengan panjang $n$ yang didefinisikan pada himpunan karakter $\Sigma$ yang memiliki larik next tepat sama dengan larik $A$ yang diberikan. Ukuran himpunan karakter adalah $m$. Keluarkan banyaknya string tersebut modulo $998\,244\,353$.

Masukan

Terdapat beberapa kasus uji dalam satu berkas uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^5$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji:

• Baris pertama berisi dua bilangan bulat $n$ ($2 \le n \le 10^5$) dan $m$ ($1 \le m \le 10^6$) yang menyatakan panjang larik yang diberikan dan ukuran himpunan karakter.
• Baris kedua berisi $n$ bilangan bulat yang dipisahkan oleh spasi, menyatakan larik $A$ yang diberikan. Dijamin bahwa $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$.

Dijamin bahwa total jumlah dari $n$ tidak melebihi $5 \times 10^5$, yaitu $\sum n \le 5 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi satu bilangan bulat, yang menyatakan banyaknya string yang memenuhi syarat, dengan jawaban diambil modulo $998\,244\,353$.

Contoh

Masukan

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

Keluaran

3
24
0

Catatan

Untuk kelompok data kedua pada contoh, misalkan himpunan karakter $\Sigma = \{'a', 'b', 'c'\}$. Ke-$24$ string yang memenuhi persyaratan adalah:

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