#D842. Levko and Strings
Levko and Strings
Levko and Strings
Levko loves strings of length n, consisting of lowercase English letters, very much. He has one such string s. For each string t of length n, Levko defines its beauty relative to s as the number of pairs of indexes i, j (1 ≤ i ≤ j ≤ n), such that substring t[i..j] is lexicographically larger than substring s[i..j].
The boy wondered how many strings t are there, such that their beauty relative to s equals exactly k. Help him, find the remainder after division this number by 1000000007 (109 + 7).
A substring s[i..j] of string s = s1s2... sn is string sisi + 1... sj.
String x = x1x2... xp is lexicographically larger than string y = y1y2... yp, if there is such number r (r < p), that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 > yr + 1. The string characters are compared by their ASCII codes.
Input
The first line contains two integers n and k (1 ≤ n ≤ 2000, 0 ≤ k ≤ 2000).
The second line contains a non-empty string s of length n. String s consists only of lowercase English letters.
Output
Print a single number — the answer to the problem modulo 1000000007 (109 + 7).
Examples
Input
2 2 yz
Output
26
Input
2 3 yx
Output
2
Input
4 7 abcd
Output
21962
inputFormat
Input
The first line contains two integers n and k (1 ≤ n ≤ 2000, 0 ≤ k ≤ 2000).
The second line contains a non-empty string s of length n. String s consists only of lowercase English letters.
outputFormat
Output
Print a single number — the answer to the problem modulo 1000000007 (109 + 7).
Examples
Input
2 2 yz
Output
26
Input
2 3 yx
Output
2
Input
4 7 abcd
Output
21962
样例
4 7
abcd
21962