Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!