AT_utpc2012_07.k番目の文字列

爱丽丝有 $n$ 张卡片，每张卡片上写着从 $\texttt{a}$ 到字母表第 $n$ 个小写字母中的一个（例如 $n=3$，那么爱丽丝就有写着 $\texttt{a}$、$\texttt{b}$、$\texttt{c}$ 的三张卡片）。爱丽丝想要将这些卡片重新排列成一个字符串。这之后，她提取出这个字符串的所有非空子串，并将它们按字典序排序。已知排序后第 $k$ 个子串是 $s$。她很好奇：有多少种满足这个条件的字符串呢？

例如，当 $n=3$ 时，如果将卡片排列成 $\texttt{cab}$，那么其子串按字典序排序后为 $\texttt{a}$、$\texttt{ab}$、$\texttt{b}$、$\texttt{c}$、$\texttt{ca}$、$\texttt{cab}$，第 $3$ 个子串是 $\texttt{b}$。而使得排序后第 $3$ 个子串为 $\texttt{b}$ 的排列有两种，分别是这种和 $\texttt{bac}$。

求所有子字符串按字典顺序排序时，第 $k$ 个字符串为 $s$ 的排列方式的数量，结果对 $10^9+7$ 取模。不过，爱丽丝可能在做梦，这样的排列方式实际上可能并不存在。在这种情况下，请输出 $0$。

第一行两个整数 $n$、$k$。

第二行一个字符串 $s$。

一行一个整数。

对 $50\%$ 的数据：$|s| \geq n-2$。其中 $|s|$ 表示字符串 $s$ 的长度。

对 $100\%$ 的数据：

• $1 \leq n \leq 26$；
• $1 \leq k \leq \frac{n(n+1)}{2}$；
• $s$ 的所有字符互不相同；
• $s$ 由字母表内第 $1 \sim n$ 个小写字母组成。

Translated by UID 781046.