В алгоритме KMP массив next (также известный как массив LPS — Longest Prefix Suffix — или префикс-функция) является ключевым понятием. Для заданной строки $S = s_1s_2\dots s_n$ длины $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]$ определяется как подстрока, образованная символами с $l$-го по $r$-й строки $S$. Считается, что $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$, и обе эти подстроки являются пустыми строками.

Дан массив $A[1..n]$ длины $n$. Вам необходимо посчитать, сколько различных строк $S$ длины $n$ над алфавитом $\Sigma$ имеют массив 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