字符串计数

题号：NC218563
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有 $n$ 张卡片，上面分别写着前 $n$ 个字母。比如 $n=3$ 的话就是 $3$ 张卡片分别写着a b c。 $n$ 张卡片的任意一种排列可以形成一个字符串， $s$ 代表这个字符串的所有子串中排名第 $k$ 个的字符串。
如 $n=3$ 时的cab,他的所有子串排名是 a ab b c ca cab 。 $k=3$ 的话s = "b"
现在给定 $n$ , $k$ , $s$ ，问你有多少个这样的字符串满足条件？
如 $n=3$ , $k=3$ , s="b"时，满足条件的字符串为cab和bac,共 $2$ 个。

输入描述:

输入第一行为一个整数，表示数据组数。
接下来每组用例第一行两个数
第二行一个字符串，中的每个字母保证一定是字母表前个字母且合法。

输出描述:

对于每组用例一行输出一个答案，答案对取模。

示例1

输入

复制

输出

复制