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 = 1000000007;
const long long UNDEF = -1;
const long long INF = 1e18;
template <typename T>
inline bool chkmax(T& aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T& aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
static char stdinBuffer[1024];
static char* stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char* stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int rint() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char rch() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
long long rlong() {
  readAhead(32);
  long long x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
const int mn = 2001;
char s[2004];
int f[2][mn][mn];
const int MSZ = mn;
typedef struct LimitedVecStruct {
  int a[MSZ];
  int sz;
  void ins(int val) { a[sz++] = val; }
} LimitedVec;
LimitedVec v[2][mn];
int id[2][mn][mn];
inline void faddint(int x, int cur, int k, int prev, int val) {
  if (id[cur][k][prev] != x) {
    id[cur][k][prev] = x;
    v[cur][k].ins(prev);
    f[cur][k][prev] = val;
  } else {
    int sum = (f[cur][k][prev] + val);
    if (sum >= MOD) sum -= MOD;
    f[cur][k][prev] = sum;
  }
}
inline void faddll(int x, int cur, int k, int prev, long long val) {
  if (id[cur][k][prev] != x) {
    id[cur][k][prev] = x;
    v[cur][k].ins(prev);
    f[cur][k][prev] = val % MOD;
  } else {
    f[cur][k][prev] = (f[cur][k][prev] + val) % MOD;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, klim;
  scanf("%d %d\n%s\n", &n, &klim, s);
  int cur = 0, nxt = 1;
  f[cur][0][0] = 1;
  v[cur][0].ins(0);
  for (int x = 1; x <= n; x++) {
    for (int k = 0; k <= klim; k++) {
      v[nxt][k].sz = 0;
    }
    int c = s[n - x] - 'a';
    for (int k = 0; k <= klim; k++) {
      int sum0 = 0;
      for (int vi = 0; vi < v[cur][k].sz; vi++) {
        int prev = v[cur][k].a[vi], cnt = f[cur][k][prev];
        if (c) {
          sum0 = (sum0 + cnt * (long long)(c)) % MOD;
        }
        if (k + prev <= klim) {
          faddint(x, nxt, k + prev, prev, cnt);
        }
        if (k + x <= klim && 25 - c > 0) {
          int key = (k + x + x <= klim) ? x : klim;
          faddll(x, nxt, k + x, key, cnt * (long long)(25 - c));
        }
      }
      if (sum0) {
        faddint(x, nxt, k, 0, sum0);
      }
    }
    swap(cur, nxt);
  }
  int ans = 0;
  for (int vi = 0; vi < v[cur][klim].sz; vi++) {
    int prev = v[cur][klim].a[vi], cnt = f[cur][klim][prev];
    ans += cnt;
    if (ans >= MOD) ans -= MOD;
  }
  printf("%d\n", ans);
}
