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 CF {

	long mod = (long) 1e9 + 7;

	void solve() {
		int n = in.nextInt();
		int k = in.nextInt();
		String s = in.next();
		long[][] dp = new long[n + 1][k + 1];
		long[][] prefSum = new long[n + 1][k + 1];
		dp[0][0] = 1;
		prefSum[0][0] = 1;
		for (int i = 0; i < n; i++)
			for (int curK = 0; curK <= k; curK++) {
				// bigger
				int cntBigger = 25 - (s.charAt(i) - 'a');
				int cntLess = 25 - cntBigger;
				int add = n - i;
				for (int cntEq = 0;; cntEq++) {
					if (add * (cntEq + 1) > curK)
						break;
					if (i - cntEq < 0)
						break;
					dp[i + 1][curK] += cntBigger
							* dp[i - cntEq][curK - add * (cntEq + 1)];
				}
				// less
				dp[i + 1][curK] += prefSum[i][curK] * cntLess; 
				dp[i + 1][curK] %= mod;
				prefSum[i + 1][curK] = (prefSum[i][curK] + dp[i + 1][curK])
						% mod;
			}
		out.println(prefSum[n][k] % mod);
	}

	FastScaner in;
	PrintWriter out;

	void run() {
		in = new FastScaner(System.in);
		out = new PrintWriter(System.out);

		solve();

		out.close();
	}

	void runWithFiles() {
		in = new FastScaner(new File("input.txt"));
		try {
			out = new PrintWriter(new File("output.txt"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}

		solve();

		out.close();
	}

	public static void main(String[] args) {
		Locale.setDefault(Locale.US);
		new CF().run();
	}

	class FastScaner {
		BufferedReader br;
		StringTokenizer st;

		FastScaner(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
		}

		FastScaner(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return null;
				st = new StringTokenizer(s);
			}
			return st.nextToken();
		}

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

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

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