喺 KMP 演算法入面，next 陣列（又叫做 LPS 陣列，即係最長公共前後綴陣列，或者失配函數）係一個核心概念。畀定一個長度為 $n$ 嘅字串 $S = s_1s_2\dots s_n$，佢嘅 next 陣列 $next[1..n]$ 定義為：$next[i]$ 表示子串 $S[1..i]$ 嘅最長相同真前綴同埋真後綴嘅長度，特別噉，$next[1] = 0$。形式化嚟講，佢嘅定義係：

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

喺度，$S[l..r]$ 定義為字串 $S$ 入面由第 $l$ 個字元到第 $r$ 個字元組成嘅子串。我哋認為對於 $\forall 1 \le i \le n$，$S[1\dots 0] = S[i+1\dots i]$，佢哋都係空字串。

畀定一個長度為 $n$ 嘅陣列 $A[1..n]$。你需要計算有幾多個定義喺字元集 $\Sigma$ 上面、長度為 $n$ 嘅唔同字串 $S$，佢嘅 next 陣列啱啱好等於畀定嘅陣列 $A$。字元集嘅大細係 $m$。請輸出滿足條件嘅字串數量對 $998\,244\,353$ 取模嘅結果。

輸入格式

單個測試檔案入面包含多組測試數據。輸入嘅第一行包含一個整數 $T$（$1 \le T \le 10^5$），表示測試數據嘅組數。

對於每組測試數據：

• 第一行包含兩個整數 $n$（$2 \le n \le 10^5$）同埋 $m$（$1 \le m \le 10^6$），分別表示畀定陣列嘅長度同埋字元集嘅大細。
• 第二行包含 $n$ 個由空格隔開嘅整數，表示畀定嘅陣列 $A$。保證對於 $\forall 1 \le i \le n$，都有 $0 \le A_i \le i - 1$。

保證所有測試數據嘅 $n$ 總和唔超過 $5 \times 10^5$，即係 $\sum n \le 5 \times 10^5$。

輸出格式

對於每組測試數據，輸出一行一個整數，表示滿足條件嘅字串數量對 $998\,244\,353$ 取模嘅結果。

樣例

輸入

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

輸出

3
24
0

說明

對於樣例入面嘅第二組數據，假設字元集 $\Sigma = \{'a', 'b', 'c'\}$。滿足要求嘅 $24$ 個字串係：

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