CF360C.Levko and Strings

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 = _s_1_s_2... s__n is string s__i__s__i  +  1... s__j.

String x  =  _x_1_x_2... x__p is lexicographically larger than string y  =  _y_1_y_2... y__p, if there is such number r (r < p), that _x_1  =  _y_1,  _x_2  =  _y_2,  ... ,  x__r  =  y__r and x__r  +  1 > y__r  +  1. The string characters are compared by their ASCII codes.

Levko 非常喜欢长度为 $n$、仅由小写英文字母组成的字符串。他拥有这样一个字符串 $s$。对于每个长度为 $n$ 的字符串 $t$，Levko 将其相对于 $s$ 的**美观度（beauty）**定义为满足如下条件的下标对 $(i, j)$（其中 $1 \le i \le j \le n$）的个数：子串 $t[i..j]$ 在字典序上严格大于子串 $s[i..j]$。

这位男孩想知道：有多少个字符串 $t$，使得其相对于 $s$ 的美观度恰好等于 $k$？请你帮助他求出这个数目对 $1000000007$（即 $10^9 + 7$）取模的结果。

字符串 $s = s_1 s_2 \dots s_n$ 的子串 $s[i..j]$ 定义为字符串 $s_i s_{i+1} \dots s_j$。

字符串 $x = x_1 x_2 \dots x_p$ 在字典序上大于字符串 $y = y_1 y_2 \dots y_p$，当且仅当存在某个整数 $r$（$r < p$），使得 $x_1 = y_1,\, x_2 = y_2,\, \dots,\, x_r = y_r$，且 $x_{r+1} > y_{r+1}$。字符之间的比较依据其 ASCII 码值进行。

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.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2000$，$0 \leq k \leq 2000$）。

第二行包含一个长度为 $n$ 的非空字符串 $s$。字符串 $s$ 仅由小写英文字母组成。

Print a single number — the answer to the problem modulo 1000000007 (109 + 7).

输出一个数字——该问题答案对 1000000007（$10^9 + 7$）取模的结果。