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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class LevkoAndStrings {
	static int N;
	static int K;
	static int[] arr;
	
	static long MOD = 1000000007;
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		StringTokenizer tk = new StringTokenizer(in.readLine());
		N = Integer.parseInt(tk.nextToken());
		K = Integer.parseInt(tk.nextToken());

		arr = new int[N];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = in.read();
		}

		// dp[i][j] = how many strings of length i, such that their accountable
		// beauty against prefix
		// of s = j
		// accountable beauty = total substrings in length N whose reasons for
		// beauty (first >) are in <=i
		// and all strings with t[i] >/</= s[i]
		int [][] dpGreater = new int[N][K+1];
		int [][] dpLess = new int[N][K+1];
		int [][] dpEq = new int[N][K+1];

		dpLess[0][0]= arr[0] - 'a';
		dpEq[0][0] = 1;
		if(N <= K)
			dpGreater[0][N] = 'z' - arr[0]; 
		
		for (int i = 1; i < N; i++) {
			int gMult = 'z' - arr[i];
			int lMult = arr[i] - 'a';
			
			
			for(int j = 0; j <= K; j++) {
				//case >
				//bruteforce on number of consecutive equals
				if(gMult != 0) {
					//beauty contributed by last el = (1+e) * (N-i)
					int prevBeauty = j - (N-i);

					//e == i case, all EQ case
					if((1+i) * (N-i) == j) {
						dpGreater[i][(1+i) * (N-i)] = 1;
					}
					for(int pi = i-1; pi >= 0 && prevBeauty >= 0; pi--) {
						dpGreater[i][j] += dpLess[pi][prevBeauty];
						if(dpGreater[i][j] >= MOD) dpGreater[i][j] -= MOD;
						dpGreater[i][j] += dpGreater[pi][prevBeauty];
						if(dpGreater[i][j] >= MOD) dpGreater[i][j] -= MOD;
						prevBeauty -= N-i;
					}
					dpGreater[i][j] = (int)(((long)gMult * dpGreater[i][j]) % MOD);
				}
				
				//case <
				//not contributing anything
				dpLess[i][j] = (int) (((long)dpLess[i-1][j] + dpEq[i-1][j] + dpGreater[i-1][j]) %MOD);
				
				//case =
				dpEq[i][j] = dpLess[i][j];
				dpLess[i][j] = (int)(((long)lMult *  dpLess[i][j]) % MOD);
			}
		}
		
		out.println(((long)dpGreater[N-1][K] + dpEq[N-1][K] + dpLess[N-1][K]) % MOD);
		out.close();
	}
	/*
if i, j, runtime = 
sum i, sum j, 
for(i)
	for(j)
		while( (1+e)(n-i) < j)
			e++
			
count = 0
for i, for j count+= j/(n-i)

for i, 1/(n-i) * for j count += j
j^2 * ln(n)
	 */
}
