Problem G
Substring Tree

Given a nonempty string, $S,$ consider the construction of a rooted tree in which each node contains a nonempty substring $\textrm{of}~ S.$ The levels of the tree are numbered $0, 1, 2, \ldots ,$ starting with the top (root) level.

• The root node contains $S.$

• For any node, $X,$ in level $\ell \geq 0,$ let $\sigma $ be the string in $X.$ The children of $X$ (which are in level $(\ell + 1))$ contain all the distinct nonempty substrings of $\sigma .$

For example, Figure 1 shows the first three levels of the substring tree with $S = \texttt{BABC}$ in the root. Note that the children of any node contain distinct strings, but the same substring of $S$ may appear more than once in a level.

Figure 1: Levels $0, 1, 2$ of substring tree with initial string $S = \texttt{BABC}$

Given $S$ and $L \geq 0,$ determine how many nodes are in $\textrm{level}~ L.$

Input

The first line of input contains two space-separated integers, $N$ and $L,$ where $N$ is the length of $S,$ the initial string $(1 \leq N \leq 50),$ and $L$ is a level in the resulting substring tree $(0 \leq L \leq 100).$ The second line contains $S$, a string of length $N$ consisting entirely of uppercase English letters (A–Z).

Output

Print a single integer, the number of nodes in $\textrm{level}~ L$ of the substring tree with initial $\textrm{string}~ S.$ Since this value can be large, output it mod $(10^9 + 7).$

4 2
BABC

32

3 5
ZZZ

21