Background

This problem comes from the original BZOJ. We acknowledge that the copyright of the statement and the original testdata belongs to the original BZOJ or to the problem author(s) who authorized BZOJ to use it. If you are the copyright holder and believe that we have infringed your rights, please contact us.

Problem Description

You are given a string $S$ of length $n$ consisting of the three characters B, W, and X. You need to recolor each X into either B or W.

For the given $k$, ask how many coloring methods make it possible that there exist integers $a, b, c, d$ satisfying:

• $1 \le a \le b < c \le d \le n$;
• $b = a + k - 1$, $d = c + k - 1$;
• $S_a = S_{a+1} = \dots = S_b = \tt B$;
• $S_c = S_{c+1} = \dots = S_d = \tt W$.

Since the number of methods may be large, you only need to output the final answer modulo $10^9 + 7$.

Input Format

The first line contains two positive integers $n, k$.

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

Output Format

Output one line containing one integer, representing the answer.

5 2
XXXXX

4

Hint

For $20\%$ of the testdata, $1 \le n \le 20$.

For $50\%$ of the testdata, $1 \le n \le 2000$.

For $100\%$ of the testdata, $1 \le n, k \le 10^6$.

Translated by ChatGPT 5