Skip to content

1044: 冰菓

题目

题目描述

有能力者的不自觉是对无能力者的讽刺。

——《冰菓》

“我很好奇!”

千反田爱瑠得到了一个长度为 $n$ 字符串 $s$,这个字符串只包含小写拉丁字母。

对于一个长度为 $n$ 的只包含小写拉丁字母的串 $t$,我们定义它和 $s$ 的相似值是满足子串 $t[i..j]$ 字典序比 $s[i..j]$ 大的下标 $i,j(1\leq i\leq j\leq n)$ 的对数

千反田爱馏想要知道,有多少个串 $t$ 满足和 $s$ 的相似值恰好为 $k$。你能帮她计算出答案吗?

由于答案可能太大,请将结果对 $10^9+7$ 取模。

输入格式

第一行是两个整数 $n$ 和 $k$。

第二行包含一个长度为 $n$ 的非空字符串 $s$,只包含小写拉丁字母。

输出格式

输出一行,表示答案模$10^9+7$的值。

样例输入

样例输入一

``` 4 7 abcd

```

样例输入二

``` 47 0 tmvdxhumdsbypyocuydhqevkgfijsbdoucgugqkruktmlem

```

样例输出

样例输出一

``` 21962

```

样例输出二

``` 129331153

```

数据范围

对于$20\%$的数据,保证$1\leq n\leq 4$。

对于$40\%$的数据,保证$1\leq n\leq 200,0\leq k\leq 200$。

对于$100\%$的数据,保证$1\leq n\leq2000,0\leq k\leq2000$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!