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;
int n, k, mod = 1000000007;
char t[2042];
long long dp[2042][2042], suff[2042][2042];
int solve() {
  dp[n][0] = 1;
  for (int cInd = n - 1; cInd >= 0; cInd--) {
    dp[cInd][0] = 1;
    for (int kLeft = 0; kLeft <= k; kLeft++) {
      bool f = 0;
      for (int d = 0; cInd + d + 1 <= n; d++) {
        if (kLeft - (n - (cInd + d)) * (d + 1) >= 0) {
          dp[cInd][kLeft] +=
              (1LL * dp[cInd + d + 1][kLeft - (n - (cInd + d)) * (d + 1)] *
               ('z' - t[d + cInd])) %
              mod;
        } else {
          f = 1;
          break;
        }
      }
      if (f) {
        for (int d = n - cInd - 1; 1; d--) {
          if (kLeft - (n - (cInd + d)) * (d + 1) >= 0) {
            dp[cInd][kLeft] +=
                (1LL * dp[cInd + d + 1][kLeft - (n - (cInd + d)) * (d + 1)] *
                 ('z' - t[d + cInd])) %
                mod;
          } else {
            f = 1;
            break;
          }
        }
      }
      dp[cInd][kLeft] +=
          (suff[cInd + 1][kLeft] + dp[cInd + 1][kLeft] * (t[cInd] - 'a')) % mod;
      dp[cInd][kLeft] %= mod;
      suff[cInd][kLeft] += (1LL * dp[cInd + 1][kLeft] * (t[cInd] - 'a') +
                            suff[cInd + 1][kLeft]) %
                           mod;
    }
  }
  return dp[0][k];
}
int main() {
  cin >> n >> k;
  cin >> t;
  cout << solve() << "\n";
  return 0;
}
