CF360C Levko and Strings

Levko 非常喜欢长度为 $n$、只包含小写英文字母的字符串。他有一个这样的字符串 $s$。对于每一个长度为 $n$ 的字符串 $t$，Levko 定义 $t$ 相对于 $s$ 的“美丽度”为满足以下条件的下标对 $(i, j)$ 的数量：$1 \leq i \leq j \leq n$，并且 $t[i..j]$ 这个子串在字典序上大于 $s[i..j]$。 Levko 想知道，有多少个字符串 $t$ 相对于 $s$ 的美丽度恰好等于 $k$。请你帮他求出这个数量对 $1000000007$（$10^9+7$） 取模的结果。 字符串 $s[i..j]$ 表示的含义是，$s = s_1s_2\ldots s_n$，则 $s[i..j]=s_is_{i+1}\ldots s_j$。 对于长度都为 $p$ 的两个字符串 $x = x_1x_2\ldots x_p$ 和 $y = y_1y_2\ldots y_p$，当存在某个 $r$（$r < p$），使得 $x_1 = y_1, x_2 = y_2, \ldots, x_r = y_r$，并且 $x_{r+1} > y_{r+1}$ 时，称 $x$ 的字典序大于 $y$。字符的比较按照它们的 ASCII 码进行。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2000$，$0 \leq k \leq 2000$）。 第二行包含一个非空字符串 $s$，长度为 $n$。字符串 $s$ 只包含小写英文字母。

输出一个整数，表示满足条件的字符串个数对 $1000000007$（$10^9+7$）取模的结果。

由 ChatGPT 5 翻译