← 返回题目列表

AtCoder · utpc2012_07

G. 第 k 个字符串

中文机器翻译题面 查看原题

問題

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