В алгоритмі 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