钟楼里的光线又暗，台阶在眼前一层层模糊成影。雨声贴着墙壁回响，她只好微微眯起眼，小步试探着往下走。他放慢了脚步，两人间的空隙被悄然填补。她看不清路，却更靠近了他一点，像是撞进了一段不可言说的心事。钟声沉沉回荡，空气里满是潮湿的安静，隐秘的情绪却已酝酿，被悉数读懂。
他们一共走下了 级台阶。每一级台阶上的脚步声、雨声与钟声交织在一起，形成一个下标从 开始的长度为 的小写字母字符串 。
为了描述钟楼中的回声，记 中第 个字符到第 个字符构成的子串为 ，记前缀 。
定义函数 表示 的最长影子长度：

即 为最大的小于 的非负整数 满足 。特别地，若不存在 满足条件，则 。
再定义函数 表示 的回声阶数：

即 或 或 时 ，否则 。
也就是说，只有当一个前缀的最长影子至少覆盖自身一半时，这段影子才足够清晰，可以继续向更深处回响。
现在你需要将整个字符串 划分成若干个非空连续片段：

一次划分被称为合法，当且仅当每个片段 都满足：
1. 存在某个整数长度 满足 ，使得 ，即每段是一个原串 的前缀。
2. 该长度的回声阶数不少于 ，即 。
请计算合法划分方案数。由于答案可能很大，请输出答案对 取模后的结果。

第一行一个整数  ，表示数据组数。
对于每组数据，第一行两个整数  。
第二行一个长度为  的仅包含小写英文字母的字符串 。
保证单个测试点内所有数据中  的和不超过 。

对于每组数据，输出一行一个整数，表示合法划分方案数对  取模后的结果。

3
5 0
ababa
4 1
aaaa
4 2
aaaa

4
2
1