Gats and the Startling String

Time limit: 2000 msMemory limit: 256 MB

Gats has a string with $N$ knots arranged from left to right. Knot $i$ has color $S_i$ .

Gats chooses exactly $K$ distinct knots. Every subset of $K$ knots is chosen with equal probability. Let their positions in increasing order be $p_1 < p_2 < \cdots < p_K.$

For each $t$ with $2 \le t \le K-1$ , the chosen knot at position $p_t$ is startled if both of the following hold:

its two neighboring chosen knots have the same color, so $S_{p_{t-1}}=S_{p_{t+1}}$ ;

The score of a choice is the number of startled knots. Find the expected score over all equally likely choices of $K$ knots.

Input

The first line contains two integers $N$ and $K$ ( $1 \le K \le N \le 5000$ ), the number of knots and the number chosen by Gats.

The second line contains a string $S$ of length . Every character of is a lowercase English letter, and is the color of the -th knot.

Output

Let $X$ be the number of startled knots after Gats makes his choice. Write the expected value as a reduced fraction $\frac{P}{Q}$ .

Print the integer $P\cdot Q^{-1}\bmod (10^9+7),$ where is the multiplicative inverse of modulo .

Samples

Sample 1

Input

5 3
ababa

Output

500000004

The ten possible choices have a total score of $5$ , so the expected score is $\frac{1}{2}$ . Its required residue is $500000004$ .

Sample 2

Input

5 4
ababa

Output

400000004

The five possible choices have a total score of , so the expected score is .

Gats and the Startling String

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions

Sample 3