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$)이 주어집니다.
- 두 번째 줄에는 주어진 배열 $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$으로 나눈 나머지를 나타내는 정수 하나를 한 줄에 출력합니다.
예제
입력
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