题目描述Description

给定一个长度为 n 且仅由小写字母组成的字符串 S，并做出如下约定。

• 子序列：从 S 中将若干元素（不一定连续）提取出来而不改变相对位置形成的序列称为子序列。

• k 松散子序列：若 S 的一个子序列中任意两个相邻字符在原串 S 中至少间隔 k 个位置，则这个子序列称为 S 的一个 k 松散子序列。具体地，对于 S 的一个长为 m 的子序列 T = \overline{S_{pos_{1}}S_{pos_{2}}\cdots S_{pos_{m}}}，T 是 S 的一个 k 松散序列当且仅当 \forall i \in [1, m - 1]，pos_{i + 1} - pos_{i} > k。

现给定一个非负整数 k，你需要求出 S 本质不同的非空 k 松散子序列数目，对 998244353 取模的结果。

称 S 的两个子序列 A 与 B 本质不同，当且仅当 |A| \neq |B| 或存在下标 i 满足 A_i \neq B_i。

输入格式Input

第一行一个整数 T（1\le T\le 10^6），代表数据组数。

对于每一组数据，第一行两个整数 n, k（1\le n \le 10^6, 0\le k \le n），意义如题目描述。

第二行一个长为 n 的字符串 S，保证仅由小写字母组成。

保证对于所有数据，\sum n \le 10^6。

输出格式Output

对于每组数据，输出一行一个整数，代表 S 本质不同的非空 k 松散子序列数目，对 998244353 取模。

样例Sample

提示Hint

对于第一组数据，子序列 a͡，b͡，a͡b 符合要求。

对于第二组数据，子序列 a͡，b͡，c͡，a͡a，a͡b，b͡b 符合要求。

出题Author

来源Source