11285: 【原1285】时晴时雨

题目

题目描述

author: Taring Lee 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1285

Description

Taring 喜欢晴天，也喜欢雨天。

Taring说：我想体验连续的K天的晴朗，去远足，去放歌；我还想再这K个晴天之后，再去体验连续的K天的云雨，去感受落雨时的轻语。这是令Taring最开心的事情了。其它的时间，Taring会在机房默默的编写着代码。

当然，Taring不想在这连续的K个晴天和连续的K个雨天里被机房的事务打扰或者被自然天气的变化中断。也就是说，这K个晴天和K个雨天必须是连续的，但是他们之间并不需要时间连续。显然的，Taring如果在感受了连续的K天晴朗后，前去机房写代码，等待下雨的时候再次开始他的感悟，这样是不会影响Taring的心情的。

Taring通过天气预报得到了最近连续 N 天中若干天的天气情况（天气情况只有“晴”和“雨”两种），但其他的天数的天气情况均是未知的。

他想知道有多少种可能的不同的天气情况（对于两种天气情况，如果有任意一天的天气情况是不一样的，就算做不同的天气情况），使他能够完成这两项体验。

Input Format

输入共有两行。

第1行有2个整数，分别表示上文中所述的N和K。

第2行是一个长度为N的字符串，仅包含有B（清），W（雨），X（未知）三种字符。

Output Format

输出一个整数Ans，表示合法的天气方案数量。

由于Ans可能很大，请将答案Mod 1,000,000,007 \((10^9 + 7)\)

Sample Input 1

4 2
XXXX

Sample Output 1

1

Sample Input 2

10 2
XXBXXWXXXX

Sample Output 2

166

Hint

对于20%的数据，N ≤ 10。

对于50%的数据，N ≤ 1,000。

对于70%的数据，K ≤ 10。

对于100%的数据，1 ≤ K ≤ N ≤ 1,000,000。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！