CF204D Little Elephant and Retro Strings

小象在阁楼上发现了一条破旧的黑白字符串 $s$。 字符串 $s$ 的字符从左到右依次编号为 $1$ 到 $|s|$，其中 $|s|$ 表示字符串的长度。我们记字符串 $s$ 的第 $i$ 个字符为 $s_{i}$。由于这是一条黑白字符串，每个字符要么是字母 "B"，要么是字母 "W"。不幸的是，这条字符串实在太旧了，有些字符已经损坏，这些位置用 "X" 表示。 小象决心要修复这条字符串，并把它挂到墙上。为此，他需要将每个 "X" 替换为 "B" 或 "W"。挂在墙上的字符串必须好看，他认为字符串是“美丽的”当且仅当其中存在两个长度为 $k$ 的不相交子串，左边的子串全是 "B"，右边的子串全是 "W"。更正式地说，存在四个整数 $a, b, c, d$，满足 $1 \leq a \leq b < c \leq d \leq |s|$，$b-a+1 = d-c+1 = k$，并且 $s_i$ 全为 "B"（$a \leq i \leq b$），$s_j$ 全为 "W"（$c \leq j \leq d$）。 请你帮助小象求出，他可以通过修复字符串 $s$ 获得多少种不同的美丽字符串。如果某两个字符串在某个位置的字符不同，则它们被认为是不同的字符串。如果字符串 $s$ 中没有字符 "X" 且它已经是美丽的，则答案为 1。 由于答案可能很大，请输出其对 $1000000007$（即 $10^{9}+7$）取模的结果。

第一行包含两个用空格分隔的整数 $n$ 和 $k$，$1 \leq k \leq n \leq 10^6$。 第二行包含长度为 $n$ 的字符串 $s$，字符串 $s$ 只包含字符 "W"、"B" 和 "X"。

输出一行，一个整数，表示答案对 $1000000007$ 取模的结果。

由 ChatGPT 5 翻译