Levko非常喜欢长度为n、由小写英文字母组成的字符串。他有一根这样的弦。对于长度为 n 的每个字符串 t,Levko 将其相对于 s 的美度定义为索引 i、j (1 ≤ i ≤ j ≤ n) 对的数量,使得子字符串 t[i..j] 按字典顺序大于子字符串 s[i..j]。
男孩想知道有多少根弦 t,使得它们相对于 s 的美恰好等于 k。帮他找出这个数除以 1000000007 (109 + 7) 后的余数。
字符串 s = s1s2... sn 的子字符串 s[i..j] 是字符串 sisi + 1... sj。
字符串 x = x1x2... xp 按字典顺序大于字符串 y = y1y2... yp,如果存在这样的数字 r (r < p),即 x1 = y1、x2 = y2、...、xr = yr 和 xr + 1 > yr + 1。字符串字符通过其 ASCII 代码进行比较。
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 2000, 0 ≤ k ≤ 2000)。
第二行包含长度为 n 的非空字符串 s。字符串 s 仅由小写英文字母组成。
输出
打印一个数字——问题的答案以 1000000007 (109 + 7) 为模。
示例
输入 #1
2 2 yz
输出 #1
26
输入 #2
2 3 yx
输出 #2
2
输入 #3
4 7 abcd
输出 #3
21962