← 返回题目列表

Codeforces · 204/D

D. 小象和复古弦

中文机器翻译题面 查看原题

小象在阁楼上发现了一根破烂的黑白旧绳子。

字符串s的字符从左到右从1到|s|编号,其中|s|是字符串的长度。我们将字符串 s 的第 i 个字符表示为 si。由于字符串是黑白的,因此字符串的每个字符要么是字母“B”,要么是字母“W”。不幸的是,该字符串非常古老,并且一些字符已损坏。损坏的位置用“X”表示。

小象决定恢复绳子并将其挂在墙上。为此,他需要将每个字符“X”替换为“B”或“W”。绳子挂在墙上一定好看,所以一定很漂亮。如果一个字符串有两个给定长度 k 的不相交的子字符串,并且左边的子串完全由字符“B”组成,右边的子串完全由字符“W”组成,那么小象认为该字符串是漂亮的。更正式地说,有四个整数 a、b、c、d (1 ≤ a ≤ b < c ≤ d ≤ |s|; b - a + 1 = d - c + 1 = k),这样 si = "B" (a ≤ i ≤ b) 且 sj = "W" (c ≤ j ≤ d)。

帮助小象找出他可以从字符串 s 中获得多少条不同的漂亮字符串。如果存在这样的位置,即第一个字符串中的字符与第二个字符串中的对应字符不同,则两个字符串被认为是不同的。如果这个字符串不包含字符 «X» 并且它已经很漂亮了 - 答案是 1。

由于答案可能相当大,因此打印它模 1000000007 (109 + 7)。

输入

第一行包含两个空格分隔的整数 n 和 k (1 ≤ k ≤ n ≤ 106)。第二行包含字符串 s。字符串 s 的长度为 n,仅由字符“W”、“B”和“X”组成。

输出

在一行上打印一个整数 — 问题的答案以 1000000007 (109 + 7) 为模。

示例

输入 #1

3 2
XXX

输出 #1

0

输入 #2

4 2
XXXX

输出 #2

1

输入 #3

10 2
XXBXXWXXXX

输出 #3

166