Gats and the Uneven Purr String

Time limit: 2000 msMemory limit: 256 MB

Gats has tied a string across $N$ knots arranged from left to right. The knot at position $i$ has color $S_i$ .

Before jumping, Gats chooses exactly $K$ distinct knots uniformly at random from all subsets of $K$ knots. He then visits the chosen knots in increasing order of position.

Let the chosen positions be

p_1 < p_2 < \ldots < p_K.

For every $t$ satisfying $2 \le t \le K-1$ , consider the three consecutive visited knots at positions $p_{t-1}$ , , and . Gats receives one fish at if both of the following conditions hold:

the incoming jump is strictly shorter than the outgoing jump: $p_t-p_{t-1} < p_{t+1}-p_t;$

Gats's score is the total number of fish he receives. Find his expected score.

Input

The first line contains two integers $N$ and $K$ ( $3 \le K \le N \le 5000$ ), the number of knots and the number of knots Gats will visit.

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

Output

Print one integer: the expected number of fish Gats receives, modulo $P=10^9+7$ .

More precisely, if the expectation is written as a fraction $a/b$ with $b \not\equiv 0 \pmod P$ , print

Samples

Sample 1

Input

4 3
abcd

Output

250000002

Exactly one of the four equally likely selections gives Gats one fish. The expected score is $\frac{1}{4}$ , represented modulo $10^9+7$ as .

Gats and the Uneven Purr String

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2