#P18070. Reverse KMP

Reverse KMP

Reverse KMP

题目描述

对长度为 nn 的字符串 ss,定义前缀函数 next⁡i\operatorname{next}_i 为最大的整数 ℓ\ell,满足

$$0\le\ell<i,\qquad s_1s_2\cdots s_\ell=s_{i-\ell+1}s_{i-\ell+2}\cdots s_i.$$

即前 ii 个字符构成的字符串的最长相等真前缀与后缀的长度,没有非空匹配时为 00。

给定数组 A1,…,AnA_1,\ldots,A_n 和包含 mm 种不同字符的字母表,求有多少个长度为 nn 的字符串,其前缀函数恰为 AA。答案对 998244353998244353 取模。数组可能不对应任何字符串,此时答案为 00。

输入格式

第一行整数 TT。每组数据第一行两个整数 n,mn,m,第二行 nn 个整数 A1,…,AnA_1,\ldots,A_n。

1≤T≤1051\le T\le10^5,2≤n≤1052\le n\le10^5,1≤m≤1061\le m\le10^6,0≤Ai≤i−10\le A_i\le i-1。所有测试用例的 nn 之和不超过 5×1055\times10^5。

输出格式

每组输出一个整数,表示字符串数量对 998244353998244353 取模的结果。

样例 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