Trong thuật toán KMP, mảng next (còn được gọi là mảng LPS - viết tắt của Longest Prefix Suffix, hay hàm thất bại) là một khái niệm cốt lõi. Cho một xâu $S = s_1s_2\dots s_n$ có độ dài $n$, mảng next của nó là $next[1..n]$ được định nghĩa sao cho $next[i]$ biểu thị độ dài của tiền tố thực sự và hậu tố thực sự bằng nhau dài nhất của xâu con $S[1..i]$, cụ thể là $next[1] = 0$. Một cách hình thức, nó được định nghĩa như sau:

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

Ở đây, $S[l..r]$ được định nghĩa là xâu con được tạo bởi ký tự thứ $l$ đến ký tự thứ $r$ của xâu $S$. Quy ước rằng $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$, cả hai đều là xâu rỗng.

Cho một mảng $A[1..n]$ có độ dài $n$. Bạn cần đếm xem có bao nhiêu xâu $S$ khác nhau có độ dài $n$ được định nghĩa trên bảng chữ cái $\Sigma$ có mảng next bằng đúng mảng $A$ đã cho. Kích thước của bảng chữ cái là $m$. Hãy in ra số lượng xâu như vậy theo modulo $998\,244\,353$.

Dữ liệu vào

Có nhiều bộ dữ liệu trong một tệp kiểm tra duy nhất. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^5$), cho biết số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu:

• Dòng đầu tiên chứa hai số nguyên $n$ ($2 \le n \le 10^5$) và $m$ ($1 \le m \le 10^6$) lần lượt biểu thị độ dài của mảng đã cho và kích thước của bảng chữ cái.
• Dòng thứ hai chứa $n$ số nguyên cách nhau bởi dấu cách, biểu thị mảng $A$ đã cho. Dữ liệu đảm bảo rằng $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$.

Dữ liệu đảm bảo rằng tổng của $n$ không vượt quá $5 \times 10^5$, tức là $\sum n \le 5 \times 10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số nguyên, biểu thị số lượng xâu thỏa mãn điều kiện, lấy kết quả theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

3
24
0

Ghi chú

Đối với nhóm dữ liệu thứ hai trong ví dụ, giả sử bảng chữ cái $\Sigma = \{'a', 'b', 'c'\}$. $24$ xâu thỏa mãn yêu cầu là:

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