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 = 1e9 + 7;
void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
int get(char x) { return 'z' - x; }
int rget(char x) { return x - 'a'; }
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  vector<vector<int>> dp(n, vector<int>(k + 1));
  for (int i = 0; i < n; ++i) {
    int c = (i + 1) * (n - i);
    if (c <= k) add(dp[i][c], get(s[i]));
    add(dp[i][0], rget(s[i]));
  }
  vector<int> sum(k + 1);
  for (int i = 0; i < n; ++i)
    for (int j = 0, l, r; j <= k; ++j) {
      dp[i][j] = (dp[i][j] + (long long)rget(s[i]) * sum[j]) % mod;
      for (l = i + 1; l < n; ++l) {
        int c = j + (l - i) * (n - l);
        if (c > k) break;
        dp[l][c] = (dp[l][c] + (long long)get(s[l]) * dp[i][j]) % mod;
      }
      for (r = n - 1; r > l; --r) {
        int c = j + (r - i) * (n - r);
        if (c > k) break;
        dp[r][c] = (dp[r][c] + (long long)get(s[r]) * dp[i][j]) % mod;
      }
      add(sum[j], dp[i][j]);
    }
  int ans = k == 0;
  for (int i = 0; i < n; ++i) add(ans, dp[i][k]);
  cout << ans << "\n";
  return 0;
}
