Alice 有 $n \le 26$ 张卡片，每张卡片上都标有前 $n$ 个小写英文字母中的一个。例如，如果 $n = 3$，Alice 有三张分别标有 “a”、“b” 和 “c” 的卡片。Alice 通过排列这些卡片构造了一个字符串 $t$。此外，她考虑了 $t$ 的所有非空子串，并将它们按字典序排序。结果发现，这个排序后的子串列表中的第 $k$ 个字符串是 $s$。问有多少种可能的 $t$？

例如，如果 $n = 3$ 且 $t = \text{cab}$，排序后的列表为 $\text{a, ab, b, c, ca, cab}$，其中第 3 个字符串是 $\text{b}$。当 $k = 3$ 且 $s = \text{b}$ 时，$t$ 有两种可能：$\text{cab}$ 和 $\text{bac}$。

计算与给定信息一致的可能的 $t$ 的数量，结果对 $10^9 + 7$ 取模。注意，Alice 可能犯了错误，这种情况下可能的 $t$ 的数量为零。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $k$。下一行包含字符串 $s$ ($1 \le n \le 26$, $1 \le k \le n(n + 1)/2$)。$s$ 中的字符互不相同；$s$ 由前 $n$ 个小写英文字母组成。

输出格式

在一行中输出答案。

样例

样例输入 1

2 2
b

样例输出 1

1

样例输入 2

3 3
b

样例输出 2

2