解题思路

1) 反向计数：总方案 − 坏方案

• 记 X 的个数为 cntX，总方案数：$2^{\text{cntX}}$。
• “坏方案”定义：最终串 没有 连续 $k$ 个 B。
• 于是答案 = $2^{\text{cntX}} - \text{bad}$ (取模)。

下面重点是线性时间统计 bad。

题目内容

给定长度为 $n$ 的字符串 $s$ ，由字符 $B$ (黑)、$W$ (白)和 $X$ (未知)组成。你需要将每个 $X$ 替换为 $B$ 或 $W$ ，得到最终字符串。如果最终字符串中存在至少一个连续长度为 $k$ 的子串，该子串全部由字符 $B$ 构成，则称该字符串为好串。

请计算有多少种不同的填充方式，使得得到的字符串为好串,并对结果取模 $10^9+7$ 后输出。

【名词解释】

• 子串为从原字符串中，连续的选择一段字符(可以全选、可以不选)得到的新字符串。

输入描述

第一行包含两个整数 $n,k(1 ≦k≦n ≤ 10^6)$ ，分别表示字符串长度、要求的连续黑色长度阈值。

第二行包含一个长度为 $n$ 的字符串 $s$ ，仅由字符 $B、W$ 和 $X$ 组成。

输出描述

输出一个整数——好串的填充方案总数对 $10^9+7$ 取模后的结果。

样例1

输入

3 2
XXX

输出

3

说明

样例说明：所有 $8$ 种填充中，包含连续"$BB$"子串的有"$BBW$"、"$BBB$”、"$WBB$"共3种。

样例2

输入

4 3
XXXX

输出

3

说明

样例说明：长度为 $4$ 的字符串，包含连续"$BBB$"的填充共有 $3$ 种。

样例3

输入

5 2
BWBWB

输出

0