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$ で割った余りを出力してください。

入力

1 つのテストファイルに複数のテストケースが含まれます。入力の最初の行には、テストケースの数を表す 1 つの整数 $T$（$1 \le T \le 10^5$）が含まれます。

各テストケースについて：

• 1 行目には、与えられた配列の長さと文字集合のサイズを表す 2 つの整数 $n$（$2 \le n \le 10^5$）と $m$（$1 \le m \le 10^6$）が含まれます。
• 2 行目には、与えられた配列 $A$ を表す $n$ 個の整数が空白区切りで含まれます。$\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$ で割った余りを表す 1 つの整数を 1 行に出力してください。

入出力例

入力

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

注記

入出力例の 2 番目のテストケースについて、文字集合を $\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