問題
Alice有n (\leq 26)张牌,每张牌上分别有
a 到字母。n位的小写字母被写了下来。比如,n=3 的话,爱丽丝有写着 a, b, c 的3张卡片。爱丽丝把这些卡片排列起来组成了一个字符串。然后,考虑这个字符串的所有非空子字符串,并将它们按字典顺序排序。此时,k位的字符串是s。
会出现这种情况的排列方式有多少种呢?
当
例如,
当分解为n=3 的时候,如果把卡片排列成 cab ,将其子字符串按字典顺序排序后,a,ab,b,c,ca,cab ,例如第3个字符串是b 。
第3个字符串是 b 的排列方式有,这种情况和bac 共两种。
当把所有子字符串按字典顺序排序时,k第几的字符串,s通过排列组合得到的方式的数量,请求模 1000000007 的结果。 但是,爱丽丝正在做梦,这种排列方式实际上可能不存在。 如果不存在,请回答 0。
入力
n k s
第一行给出卡片的数量 n 和 按字典顺序比较k 用空格分隔。 下一行给出字符串 s 。(长度为n)
出力
将答案的数字输出在一行。
制約
- 1\leq n \leq 26
- 1\leq k \leq n(n+1)/2
- s的所有字符彼此不同
- s由字母表中第 1 到 n 个小写字母组成
部分点
针对该问题的判断设置了一组50分的测试用例。该组中包含的测试用例输入还满足以下条件。
- |s| \geq n-2。但是|s| 是字符串s的长度。
入力例 1
2 2 b
输入示例 1 的输出示例
1
入力例 2
3 3 b
输入示例 2 的输出示例
2
入力例 3
3 4 ba
输入示例 3 的输出示例 一直到
1
入力例 4
26 300 utpc
输入示例 4 对应的输出示例
831387601