F. Word Inventing
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Shakespeare is writing a new play, but he's struggling to think of what word to use next, so he wants to invent one! To do this, he will start with a given word $$$s$$$, and will perform the following operation any number of times:

  • Choose an index $$$i$$$ ($$$1 \leq i \leq n - k$$$) and swap the characters in $$$s$$$ at indices $$$i$$$ and $$$i+k$$$.

Shakespeare wants to know how many distinct words he can construct after any number of operations (possibly none). Unfortunately, Shakespeare doesn't have a computer and he is low on time, so he needs you to do this for him. Since there may be many strings, output this number modulo $$$10^9+7$$$.

Input

The first line of input will contain integers $$$n$$$ and $$$k\ (1 \leq k \leq n \leq 10^6$$$). The second line will contain string $$$s$$$, consisting of $$$n$$$ lowercase English characters.

Output

Output one line containing the answer to the problem (modulo $$$10^9+7$$$).

Examples
Input
4 2
aabb
Output
4
Input
4 1
utpc
Output
24
Input
26 5
abcdefghijklmnopqrstuvwxyz
Output
299198957