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;
__inline bool nextInt(int &val) {
  char ch;
  int sgn = 1;
  while ((ch = getchar()) != EOF) {
    if (ch == '-') sgn = -1;
    if (ch >= '0' && ch <= '9') break;
  }
  if (ch == EOF) return false;
  val = (int)(ch - '0');
  while (true) {
    ch = getchar();
    if (ch >= '0' && ch <= '9') {
      val = 10 * val + (int)(ch - '0');
    } else
      break;
  }
  val *= sgn;
  return true;
}
__inline bool nextString(string &s) {
  char ch;
  while ((ch = getchar()) != EOF) {
    if (ch >= 33 && ch <= 126) break;
  }
  if (ch == EOF) return false;
  s = string(1, ch);
  while (true) {
    ch = getchar();
    if (ch >= 33 && ch <= 126) {
      s = s + string(1, ch);
    } else
      break;
  }
  return true;
}
int n, k, dp[3888][3888], sdp[3888][3888], modul = 1000000007;
char s[3888];
int main() {
  ios_base::sync_with_stdio(false);
  scanf("%d%d", &n, &k);
  scanf("%s", s);
  memset(dp, 0, sizeof(dp));
  ;
  memset(sdp, 0, sizeof(sdp));
  ;
  dp[n - 1][1] = 'z' - s[n - 1];
  dp[n - 1][0] = s[n - 1] - 'a' + 1;
  for (int i = (2); i < (3888); i++) dp[n - 1][i] = 0;
  dp[n][0] = 1;
  for (int i = (1); i < (3888); i++) dp[n][i] = 0;
  sdp[n - 1][0] = (s[n - 1] - 'a') * dp[n][0] + sdp[n][0];
  int K = k;
  for (int is = (n - 2); is >= 0; is--) {
    for (int k = 0; k < (K + 1); k++) {
      int &ret = dp[is][k];
      ret = 0;
      int L = n - is;
      int tmp = dp[is + 1][k];
      ret =
          ((((long long)(tmp)) * ((long long)(((int)(s[is] - 'a'))))) % modul);
      if (k >= L) {
        tmp = dp[is + 1][k - L];
        tmp = ((((long long)(tmp)) * ((long long)(((int)('z' - s[is]))))) %
               modul);
        {
          ret += tmp;
          if (ret >= modul) ret -= modul;
        };
      }
      if (k == 0) {
        ret += 1;
        if (ret >= modul) ret -= modul;
      };
      {
        ret += sdp[is + 1][k];
        if (ret >= modul) ret -= modul;
      };
      int low = is, high = n - 2;
      for (low = is; low < n - 1; low++) {
        int ns = low;
        if (ns < n - 1) {
          int x = (n - ns - 1) * (ns - is + 2);
          if (k >= x) {
            tmp = dp[ns + 2][k - x];
            tmp = ((((long long)(tmp)) *
                    ((long long)(((int)('z' - s[ns + 1]))))) %
                   modul);
            {
              ret += tmp;
              if (ret >= modul) ret -= modul;
            };
          } else {
            break;
          }
        }
      }
      if (n - 1 > low) {
        for (high = n - 2; high > low; high--) {
          int ns = high;
          if (ns < n - 1) {
            int x = (n - ns - 1) * (ns - is + 2);
            if (k >= x) {
              tmp = dp[ns + 2][k - x];
              tmp = ((((long long)(tmp)) *
                      ((long long)(((int)('z' - s[ns + 1]))))) %
                     modul);
              {
                ret += tmp;
                if (ret >= modul) ret -= modul;
              };
            } else {
              break;
            }
          }
        }
      }
      tmp = ((((long long)(dp[is + 1][k])) *
              ((long long)(((int)(s[is] - 'a'))))) %
             modul);
      sdp[is][k] = sdp[is + 1][k];
      {
        sdp[is][k] += tmp;
        if (sdp[is][k] >= modul) sdp[is][k] -= modul;
      };
    }
  }
  int ret = dp[0][k];
  printf("%d\n", ret);
  return 0;
}
