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;
const int mod = (int)1e9 + 7;
int n, K, dp[2005][2005][2], dpsum[2005][2005];
char S[2005];
inline int mul(long long a, long long b) {
  a = a * b % mod;
  return a;
}
inline int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
int main(int argc, char const *argv[]) {
  cin >> n >> K >> (S + 1);
  n = strlen(S + 1);
  dp[n][0][0] = S[n] - 'a', dp[n][1][1] = 'z' - S[n], dpsum[n][0] = dp[n][0][0];
  for (int(i) = (int)(n - 1); (i) >= (int)(1); --(i))
    for (int(j) = (int)(0); (j) <= (int)(K); ++(j)) {
      dpsum[i][j] = dpsum[i + 1][j];
      for (int(k) = 0; (k) < (int)(2); ++(k)) {
        if (k == 1 && j == n - i + 1) {
          dp[i][j][k] = add(dp[i][j][k], 'z' - S[i]);
        }
        if (!k && !j) dp[i][j][k] = add(dp[i][j][k], S[i] - 'a');
        if (!k) {
          dp[i][j][k] = add(dp[i][j][k], mul(dpsum[i + 1][j], S[i] - 'a'));
        } else if (j - (n - i + 1) >= 0) {
          dp[i][j][k] =
              add(dp[i][j][k], mul(dpsum[i + 1][j - (n - i + 1)], 'z' - S[i]));
        }
        {
          int pnxt = i;
          for (int(nxt) = (int)(i + 1); (nxt) <= (int)(n); ++(nxt)) {
            int t = j - (nxt - i - 1) * (n + 1 - nxt);
            if (t < 0) break;
            pnxt = nxt;
            if (k) {
              t -= n + 1 - i;
              if (t >= 0) {
                dp[i][j][k] = add(dp[i][j][k], mul(dp[nxt][t][1], 'z' - S[i]));
              }
            } else {
              dp[i][j][k] = add(dp[i][j][k], mul(dp[nxt][t][1], S[i] - 'a'));
            }
          }
          for (int(nxt) = (int)(n); (nxt) >= (int)(pnxt + 1); --(nxt)) {
            int t = j - (nxt - i - 1) * (n + 1 - nxt);
            if (t < 0) break;
            if (k) {
              t -= n + 1 - i;
              if (t >= 0) {
                dp[i][j][k] = add(dp[i][j][k], mul(dp[nxt][t][1], 'z' - S[i]));
              }
            } else {
              dp[i][j][k] = add(dp[i][j][k], mul(dp[nxt][t][1], S[i] - 'a'));
            }
          }
        }
        if (!k) dpsum[i][j] = add(dpsum[i][j], dp[i][j][k]);
      }
    }
  int res = K == 0;
  for (int(i) = (int)(1); (i) <= (int)(n); ++(i))
    for (int(j) = (int)(0); (j) <= (int)(K); ++(j))
      for (int(k) = 0; (k) < (int)(2); ++(k)) {
        int t = j + (k ? (i - 1) * (n - i + 1) : 0);
        if (t == K) res = add(res, dp[i][j][k]);
      }
  cout << res << endl;
  return 0;
}
