CF204D.Little Elephant and Retro Strings

The Little Elephant has found a ragged old black-and-white string s on the attic.

The characters of string s are numbered from the left to the right from 1 to |s|, where |s| is the length of the string. Let's denote the i-th character of string s as s__i. As the string is black-and-white, each character of the string is either letter "B", or letter "W". Unfortunately, the string is very old and some characters are damaged. The damaged positions are denoted as "X".

The Little Elephant in determined to restore the string and hang it on the wall. For that he needs to replace each character "X" by a "B" or a "W". The string must look good on the wall, so it must be beautiful. The Little Elephant considers a string beautiful if it has two non-intersecting substrings of a given length k, such that the left one fully consists of characters "B", and the right one fully consists of characters "W". More formally, there are four integers a, b, c, d (1 ≤ a ≤ b < c ≤ d ≤ |s|; b - a + 1 = d - c + 1 = k) such that s__i = "B" (a ≤ i ≤ b) and s__j = "W" (c ≤ j ≤ d).

Help the Little Elephant find the number of different beautiful strings he can obtain from string s. Two strings are considered different if there is such position, where the character in the first string differs from the corresponding character in the second string. If this string doesn't contain characters «X» and it is already beautiful — the answer is 1.

As the answer can be rather large, print it modulo 1000000007 (109 + 7).

小象在阁楼上发现了一条破旧的黑白字符串 $s$。

字符串 $s$ 的字符从左到右编号为 $1$ 到 $|s|$，其中 $|s|$ 表示字符串的长度。记字符串 $s$ 的第 $i$ 个字符为 $s_i$。由于该字符串是黑白的，每个字符要么是字母 "B"，要么是字母 "W"。不幸的是，该字符串非常陈旧，部分字符已损坏。损坏的位置用字符 "X" 表示。

小象决心修复该字符串并将其悬挂在墙上。为此，他需将每个字符 "X" 替换为 "B" 或 "W"。字符串必须在墙上看起来美观，即它必须是“优美的”。小象认为一个字符串是优美的，当且仅当它包含两个不相交的、长度均为 $k$ 的子串：左侧子串完全由字符 "B" 组成，右侧子串完全由字符 "W" 组成。更准确地说，存在四个整数 $a,\,b,\,c,\,d$（满足 $1 \le a \le b < c \le d \le |s|$，且 $b - a + 1 = d - c + 1 = k$），使得对所有 $i \in [a, b]$ 有 $s_i = \text{"B"}$，且对所有 $j \in [c, d]$ 有 $s_j = \text{"W"}$。

请帮助小象计算：通过替换所有 "X" 字符，能获得多少种不同的优美字符串？若两个字符串在某个位置上的字符不同，则视为不同字符串。若原字符串中不含 "X" 且本身已是优美的，则答案为 $1$。

由于答案可能非常大，请输出其对 $1000000007$（即 $10^9 + 7$）取模的结果。

The first line contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 106). The second line contains string s. String s has length n and only consists of characters "W", "B" and "X".

第一行包含两个以空格分隔的整数 $n$ 和 $k$（$1 ≤ k ≤ n ≤ 10^6$）。第二行包含字符串 $s$。字符串 $s$ 的长度为 $n$，且仅由字符 "W"、"B" 和 "X" 组成。

On a single line print an integer — the answer to the problem modulo 1000000007 (109 + 7).

在一行中输出一个整数——该问题答案对 1000000007（$10^9 + 7$）取模的结果。