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.*;
import java.util.*;

public class C {

	void solve() throws IOException {
		int n = nextInt();
		int k = nextInt();
		String s = new StringBuilder(next()).reverse().toString();
		int[] a = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			a[i] = s.charAt(i - 1) - 'a';
		}

		long[][][] dp = new long[3][n + 1][k + 2];
		dp[0][1][0] = a[1];
		dp[1][1][0] = 1;
		dp[2][1][1] = 25 - a[1];

		long mod = (long) (1e+9 + 7);
		long[] sum0 = new long[k + 1];
		sum0[0] = dp[0][1][0];

		for (int i = 2; i <= n; i++) {
			for (int j = 0; j <= k; j++) {
				dp[0][i][j] = (dp[0][i - 1][j] + dp[1][i - 1][j] + dp[2][i - 1][j])
						* a[i];
				dp[0][i][j] %= mod;
				if (j >= i) {
					dp[2][i][j] = (dp[0][i - 1][j - i] + dp[1][i - 1][j - i] + dp[2][i - 1][j
							- i])
							* (25 - a[i]);
					dp[2][i][j] %= mod;
				}
				dp[1][i][j] += sum0[j];
				// for (int t = 1; t < i; t++) {
				// dp[1][i][j] += dp[0][t][j];
				// }

				int t = 1;
				int l = i - 1;
				;

				while (t < i) {
					if (t * (i - t + 1) <= j) {
						dp[1][i][j] += dp[2][t][j - t * (i - t)];
					} else {
						break;
					}
					t++;
				}
				while (l > t && l > 0) {
					if (l * (i - l + 1) <= j) {
						dp[1][i][j] += dp[2][l][j - l * (i - l)];
					} else {
						break;
					}
					l--;
				}

				if (j == 0) {
					dp[1][i][j]++;
				}
				dp[1][i][j] %= mod;
				sum0[j] = (dp[0][i][j] + sum0[j]) % mod;
			}
		}
		out.println((dp[0][n][k] + dp[1][n][k] + dp[2][n][k]) % mod);

	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new C().run();
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st;

	String next() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String temp = in.readLine();
			if (temp == null) {
				return null;
			}
			st = new StringTokenizer(temp);
		}
		return st.nextToken();
	}

	int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	long nextLong() throws IOException {
		return Long.parseLong(next());
	}

}
