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

import java.text.DecimalFormat;
import java.util.*;
import java.io.*;

public class Main {
    private static final int mod = 1000000007;
    private static char [] S;
    private static int [] less;
    private static int n,K;
    private static Integer [] [] [] dp;

    private static int add(int a,int b) {
        a += b;
        if (a >= mod) a -= mod;
        return a;
    }
    private static int mul(int a,int b ){
        long ret = (a*(long)b)%mod;
        return (int)ret;
    }
    private static int solve(int p,int ctr,int r){
        if (p == n)  return (r == 0) ? 1 : 0;
        if (dp[p][ctr][r] != null) return dp[p][ctr][r];

        int ret = solve(p+1,ctr+1,r);
        ret = add(ret,mul(solve(p+1,0,r),less[p]));
        long v = (ctr + 1L)*(n-p);
        if (v <= r)
            ret = add(ret,mul(solve(p+1,0,r-(int)v),25-less[p]));
        dp[p][ctr][r] = ret;
        return ret;
    }
    private static int solve() {
        int [] [] dp = new int[n+1][K+1];
        dp[n][0] = 1;
        for (int r = 0;r <= K;r++) {
            int contrib = 0;

            for (int p = n-1;p >= 0;p--){
                contrib = add(contrib,mul(less[p],dp[p+1][r]));
                int ret = contrib;
                if (r == 0)
                    ret++;

                int m = n-p,lim = (m + 1)/2;
                for (int i = 0;i < lim && (i+1L)*(m-i) <= r;i++) {
                    int j = p + i;
                    int v = (i+1)*(n-j);
                    ret = add(ret,mul(25-less[j],dp[j+1][r-v]));

                    if(i < m/2) {
                        j = p + n - j - 1;
                        ret = add(ret, mul(25 - less[j], dp[j + 1][r - v]));
                    }
                }

                dp[p][r] = ret;
            }
        }
        return dp[0][K];
    }
    private static void init(){
        less = new int[S.length];
        for (int i = 0;i < n;i++)
            less[i] = S[i] - 'a';
//       dp = new Integer[n][n+1][K+1];
    }

    private static void test(){
        Random rnd = new Random();
        int N = 10,lK = 10;
        for (int t = 0;t < 1000;t++) {
            n = (rnd.nextInt()%N + N)%N + 1;
            K = (rnd.nextInt()%lK + lK)%lK;
            S = new char[n];
            for (int i = 0;i < n;i++)
                S[i] = (char)('a' + (rnd.nextInt()%3 + 3)%3);
            init();
            if (solve() != solve(0,0,K)) {
                System.err.println("failed on");
                System.err.println(n + " " + K);
                System.err.println(S);
                System.err.println("expected " + solve(0,0,K)
                + " found " + solve());
                return;
            }
        }
        System.err.println("passed :)");
    }

    public static void main(String[] args) throws Exception {
        IO io = new IO(null, null);
        n = io.getNextInt();
        K = io.getNextInt();
        S = io.getNext().toCharArray();
        init();
        io.println(solve());
        io.close();
    }


}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}
