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;
template <typename T>
T Abs(T first) {
  return (first < 0 ? -first : first);
}
template <typename T>
T Sqr(T first) {
  return (first * first);
}
string plural(string s) {
  return (int((s).size()) && s[int((s).size()) - 1] == 'x' ? s + "en"
                                                           : s + "s");
}
const int INF = (int)1e9;
const long double EPS = 1e-9;
const long double PI = acos(-1.0);
bool Read(int &first) {
  char c, r = 0, n = 0;
  first = 0;
  for (;;) {
    c = getchar();
    if ((c < 0) && (!r)) return (0);
    if ((c == '-') && (!r))
      n = 1;
    else if ((c >= '0') && (c <= '9'))
      first = first * 10 + c - '0', r = 1;
    else if (r)
      break;
  }
  if (n) first = -first;
  return (1);
}
int main() {
  if (0) freopen("in.txt", "r", stdin);
  int N, K;
  int i, j, k, c, d, ans = 0, j2, k2;
  long long v;
  char S[2005];
  static int dyn[2001][2001], sum[2001];
  Read(N), Read(K);
  scanf("%s", &S);
  dyn[0][0] = 1;
  for (i = 0; i < N + 1; i++)
    for (j = (K + 1) - 1; j >= 0; j--) {
      if (i) {
        c = S[i - 1] - 'a';
        dyn[i][j] = (dyn[i][j] + (long long)c * sum[j]) % 1000000007;
      }
      if (d = dyn[i][j]) {
        if (j == K) {
          ans += d;
          if (ans >= 1000000007) ans -= 1000000007;
        }
        if (i == N) continue;
        for (k = i; k <= N - 1; k++) {
          j2 = j + (k - i + 1) * (N - k);
          if (j2 > K) break;
          c = 'z' - S[k];
          dyn[k + 1][j2] = (dyn[k + 1][j2] + (long long)c * d) % 1000000007;
        }
        k2 = k;
        for (k = N - 1; k >= k2; k--) {
          j2 = j + (k - i + 1) * (N - k);
          if (j2 > K) break;
          c = 'z' - S[k];
          dyn[k + 1][j2] = (dyn[k + 1][j2] + (long long)c * d) % 1000000007;
        }
      }
      sum[j] += dyn[i][j];
      if (sum[j] >= 1000000007) sum[j] -= 1000000007;
    }
  printf("%d\n", ans);
  return (0);
}
