Levko and Strings

题意翻译

给一个为$n$的只有小写字母组成的串$s$，定义它与一个长度为n的串$t$的的美丽度为：c存在多少个二元组$(i,j) \ 1\leq i \leq j \leq n$满足 $s[i...j] < t[i...j]$，这里的'<'是字典序比较。求有多少个t，使得s与t的美丽度为k。 $n,k \leq 2000$

题目描述

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 $ $ (10^{9}+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&lt;p $ ), that $ x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{r}=y_{r} $ and $ x_{r+1}&gt;y_{r+1} $ . The string characters are compared by their ASCII codes.

输入输出格式

输入格式

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.

输出格式

Print a single number — the answer to the problem modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

2 2
yz

输出样例 #1

26

输入样例 #2

2 3
yx

输出样例 #2

2

输入样例 #3

4 7
abcd

输出样例 #3

21962