Given a string $S$ of length $N$ consisting of the characters B, W, and X, you need to color each X as either B or W.

For a given $K$, find the number of ways to color the string such that there exist integers $a, b, c, d$ satisfying:

• $1 \leq a \leq b < c \leq d \leq N$
• $S_a, S_{a+1}, \dots, S_b$ are all B
• $S_c, S_{c+1}, \dots, S_d$ are all W

where $b = a + K - 1$ and $d = c + K - 1$.

Since the number of ways can be large, output the result modulo $10^9 + 7$.

Input

The first line contains two positive integers $N$ and $K$.

The second line contains a string $S$ of length $N$.

Output

Output a single integer representing the answer modulo $10^9 + 7$.

Examples

Input 1

5 2
XXXXX

Output 1

4

Constraints

For $20\%$ of the data, $N \leq 20$.

For $50\%$ of the data, $N \leq 2\,000$.

For $100\%$ of the data, $1 \leq N \leq 10^6$, $1 \leq K \leq 10^6$.