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
#include <bits/stdc++.h>
using namespace std;
string str;
long long dp[2010][2010], difs[2010], N, K, sums[2010][2010];
long long solve(int n, int k);
long long getSum(int n, int k) {
  if (n == N) return 0;
  long long &c = sums[n][k];
  if (c != -1) return c;
  return c = ((str[n - 1] - 'a') * solve(n, k) + getSum(n + 1, k)) %
             1000000007LL;
}
long long solve(int n, int k) {
  if (k < 0) return 0;
  if (!k) return difs[N - n];
  if (n == N) return 0;
  long long &c = dp[n][k];
  if (c != -1) return c;
  int l = -1;
  c = getSum(n + 1, k);
  for (int i = int(0); i < int(N - n); i++) {
    int v = k - (i + 1) * (N - n - i);
    if (v < 0) break;
    c = (c + ('z' - str[n + i]) * solve(n + i + 1, v) % 1000000007LL) %
        1000000007LL;
    l = i;
  }
  for (int i = N - n - 1; i >= 0; i--) {
    if (i == l) break;
    int v = k - (i + 1) * (N - n - i);
    if (v < 0) break;
    c = (c + ('z' - str[n + i]) * solve(n + i + 1, v) % 1000000007LL) %
        1000000007LL;
  }
  return c;
}
int main() {
  while (cin >> N >> K) {
    memset(dp, -1, sizeof(dp));
    memset(sums, -1, sizeof(sums));
    cin >> str;
    difs[0] = 1;
    for (int i = int(1); i < int(str.length() + 1); i++) {
      difs[i] = (difs[i - 1] * (str[N - i] - 'a' + 1LL)) % 1000000007LL;
    }
    cout << solve(0, K) << endl;
  }
  return 0;
}
