题目描述

对于一个长度为 $n$ 的字符串 $s$，对于$1 \leq i \leq n$，$next_i$ 为最大的整数 $k$，满足 $S[1:k]=S[i-k+1:i]$（若不存在这样的 $k$，则$next_i=0$）。

给出 $NEXT$ 数组和字符集大小 $m$，请问有多少个长度为 $n$ 的字符串满足其 $next$ 数组和 $NEXT$ 恰好一致，答案对 $998244353$ 取模。

输入格式

第一行一个正整数 $T$，表示数据组数。

接下来对于每组数据，第一行两个正整数 $n,m$。

第二行包含 $n$ 个整数，表示 $NEXT$ 数组。

输出格式

对于每组数据，输出一行，包含一个整数，表示答案。

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

详见下发文件，依次符合数据范围中每个测试点的性质。

详见下发文件，依次符合数据范围中每个测试点的性质。

详见下发文件，依次符合数据范围中每个测试点的性质。

详见下发文件，依次符合数据范围中每个测试点的性质。

详见下发文件，依次符合数据范围中每个测试点的性质。

详见下发文件，依次符合数据范围中每个测试点的性质。

详见下发文件，依次符合数据范围中每个测试点的性质。

详见下发文件，依次符合数据范围中每个测试点的性质。

说明提示

数据范围

对于 $100\%$ 的数据，$1\leq n\leq10^5,1\leq m\leq10^5,0\leq NEXT_i\leq i-1,1\leq T\leq10$。