P10593 BZOJ2958 Sequence Coloring

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.

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$.

The first line contains two positive integers $n, k$. The second line contains a string $S$ of length $n$.

Output one line containing one integer, representing the answer.

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