小象在阁楼上发现了一根破烂的黑白旧绳子。
字符串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