Little Elephant and Retro Strings

题意翻译

小象在阁楼上发现一个衣衫褴褛的黑白相间的字符串。 字符串s的字符从左到右编号为 1到|S| ，其中| s | 是字符串的长度。让我们将字符串s的第i个字符表示为$s_i$。由于字符串是黑白的，字符串的每个字符都是字母“ $B$ ”或字母“ $W$ ”。不幸的是，字符串很旧，有些字符被损坏。损坏的位置标记为“ $X$ ”。 小象决定复原这个字符串并将其挂在墙上。为此，他需要用“ $B$ ”或“ $W $” 替换每个字符“$ X$ ”。弦必须在墙上看起来很好，所以它必须是美丽的. 定义一个字符串是美丽的,当且仅当对于给定的K,它有两个不相交的子串使得在左侧的只包含字符$B$,右侧的只包含字符$W$. 具体地: 存在一个四元组$(a,b,c,d)(1 <= a <= b < c <= d < |s|$ &&$ b - a = d - c$,满足 $s_i = B(a <= i <= b)$ && $s_i = W( c <= i <= d)$ 帮助小象找到他可以从字符串s获得的不同美丽字符串的数量。两个字符串被认为是不同的,当且仅当存在至少一个位置使得第一个字符串中的字符与第二个字符串对应的字符不同.如果这个字符串不包含字符$X$而且它已经是美丽的了,答案是$1$。 由于答案可能相当大，请输出答案对$10^9+7$取模的值. 输入: 第一行包含两个空间分开的整数$n$和$k$ $1<=k<=n <=10^6$。第二行包含字符串s。字符串s的长度为n，只包含字符“ W ”，“ B ”和“ X ”。 输出: 一行,一个整数表示答案. 感谢@Maniac丶坚果 提供的翻译

题目描述

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 $ $ (10^{9}+7) $ .

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ and $ k $ $ (1<=k<=n<=10^{6}) $ . The second line contains string $ s $ . String $ s $ has length $ n $ and only consists of characters "W", "B" and "X".

输出格式

On a single line print an integer — the answer to the problem modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

3 2
XXX

输出样例 #1

0

输入样例 #2

4 2
XXXX

输出样例 #2

1

输入样例 #3

10 2
XXBXXWXXXX

输出样例 #3

166