Problem3051--Levko and Strings

3051: Levko and Strings

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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≤ijn), 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

Source/Category