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 mo = 1000000007;
inline int IN() {
  char ch;
  (ch = getchar());
  int f = 0, x = 0;
  for (; ((ch) == '\n' || (ch) == '\r' || (ch) == '\t' || (ch) == ' ');
       (ch = getchar()))
    ;
  if (ch == '-') f = 1, (ch = getchar());
  for (; !((ch) == '\n' || (ch) == '\r' || (ch) == '\t' || (ch) == ' ');
       (ch = getchar()))
    x = x * 10 + ch - '0';
  return (f) ? (-x) : (x);
}
int sm = 'a', bg = 'z', n, f[2005][2005], K;
char st[2005];
int large(char x) { return bg - x; }
int small(char x) { return x - sm; }
int main() {
  scanf("%d%d", &n, &K);
  scanf("%s", st + 1);
  f[0][0] = 1;
  int ans = 0;
  for (int j = (int)0; j <= (int)K; j++) {
    int sum = f[0][j];
    for (int i = (int)1; i <= (int)n; i++) {
      f[i][j] = (f[i][j] + 1ll * sum * small(st[i])) % mo;
      sum = (sum + f[i][j]) % mo;
    }
    for (int i = (int)1; i <= (int)n; i++) {
      for (int k = (int)1; k <= (int)i; k++) {
        int cost = (n - i + 1) * k;
        if (cost + j > K) break;
        f[i][cost + j] =
            (f[i][cost + j] + 1ll * f[i - k][j] * large(st[i])) % mo;
      }
    }
  }
  for (int i = (int)0; i <= (int)n; i++) ans = (ans + f[i][K]) % mo;
  printf("%d\n", ans);
  return 0;
}
