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>
void __read(T &a) {
  cin >> a;
}
template <typename T, typename... Args>
void __read(T &a, Args &...args) {
  cin >> a;
  __read(args...);
}
constexpr long long M7 = 1000000007ll;
constexpr long long M9 = 1000000009ll;
constexpr long long MFFT = 998244353ll;
template <class T>
void outv(T &a) {
  for (auto &x : a) cout << x << ' ';
}
static mt19937 rnd(static_cast<unsigned>(
    chrono::steady_clock::now().time_since_epoch().count()));
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr));
long long solve1(long long n, long long k, string s) {
  if (k == 0) {
    long long res = 1;
    for (long long i = 0; i < n; ++i) {
      res = (res * (s[i] - 'a' + 1)) % M7;
    }
    return res;
  }
  n = s.length();
  vector<vector<long long>> dp[2];
  dp[0] = dp[1] = vector<vector<long long>>(n, vector<long long>(k + 1));
  dp[0][n - 1][0] = s.back() - 'a' + 1;
  dp[1][n - 1][1] = 26 - dp[0][n - 1][0];
  long long res = 0;
  for (long long i = n - 1; i > 0; --i) {
    long long d = n - i;
    for (long long j = 0; j <= k; ++j) {
      if (j + d + 1 <= k) {
        dp[1][i - 1][j + d + 1] =
            (dp[1][i - 1][j + d + 1] + (dp[0][i][j]) * ('z' - s[i - 1])) % M7;
      }
      dp[0][i - 1][j] =
          (dp[0][i - 1][j] + dp[0][i][j] * (s[i - 1] - 'a' + 1)) % M7;
      for (long long q = 1; j + (q - 1) * d <= k && q <= i + 1; ++q) {
        if (i >= q) {
          dp[0][i - q][j + (q - 1) * d] =
              (dp[0][i - q][j + (q - 1) * d] + dp[1][i][j] * (s[i - q] - 'a')) %
              M7;
          long long nj = j + (q - 1) * d + (n - i + q);
          if (nj <= k) {
            dp[1][i - q][nj] =
                (dp[1][i - q][nj] + dp[1][i][j] * ('z' - s[i - q])) % M7;
          }
        } else if (j + (q - 1) * d == k) {
          res = (res + dp[1][i][j]) % M7;
        }
      }
    }
  }
  return (dp[0][0][k] + dp[1][0][k] + res) % M7;
}
vector<string> ss;
void generateAllString(long long n) {
  vector<long long> a(n);
  while (true) {
    string s;
    for (long long i = 0; i < n; ++i) {
      s.push_back('a' + a[i]);
    }
    ss.push_back(move(s));
    long long j = n - 1;
    while (j >= 0 && a[j] == 25) {
      j--;
    }
    if (j < 0) {
      break;
    }
    a[j++]++;
    while (j < n) {
      a[j++] = 0;
    }
  }
}
long long solve2(long long n, long long k, string s) {
  long long ans = 0;
  for (auto &t : ss) {
    long long z = 0;
    for (long long i = 0; i < n; ++i) {
      string s1, t1;
      for (long long j = i; j < n; ++j) {
        s1.push_back(s[j]);
        t1.push_back(t[j]);
        if (t1 > s1) {
          z++;
        }
      }
    }
    if (z == k) {
      ans++;
    }
  }
  return ans;
}
int32_t main() {
  long long n, k;
  __read(n, k);
  string s;
  __read(s);
  cout << solve1(n, k, s);
  return 0;
}
