Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

C. Levko and Strings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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