19377번 - K-th String 다국어

문제

Alice has $n \le 26$ cards, and each card is labeled with one of the first $n$ lowercase English letters. For example, if $n = 3,ドル Alice has three cards that are labeled "a'', "b'', and "c''. Alice constructed a string $t$ by permuting these cards. Furthermore, she considered all non-empty substrings of $t$ and sorted them lexicographically. It turned out that the $k$-th string in this sorted list of substrings was $s$. How many $t$'s are possible?

For example, if $n = 3$ and $t = cab,ドル the sorted list is a, ab, b, c, ca, cab, and the third string in the sorted list is b. When $k = 3$ and $s = b,ドル there are two possibilites for $t$: cab and bac.

Compute the number of possible $t$'s that are consistent with the given information, modulo 10ドル^9 + 7$. Note that Alice may have made mistakes, in which case the number of possible $t$'s is zero.

입력

On the first line, you are given two space-separated integers $n$ and $k$. On the next line, you are given the string $s$ (1ドル \le n \le 26,ドル 1ドル \le k \le n (n + 1) / 2$). The characters in $s$ are pairwise distinct; $s$ consists of the first $n$ lowercase English letters.

출력

Print the answer on a single line.

제한

힌트