题目描述
给出一个长度为 n,由 B,W,X 三种字符组成的字符串 S,你需要把每一个 X 染成 B 或 W 中的一个。
对于给出的 k,问有多少种染色方式使得存在整数 a,b,c,d 使得:
- 1≤a≤b<c≤d≤n。
- b=a+k−1,d=c+k−1
- Sa=Sa+1=⋯=Sb=B
- Sc=Sc+1=⋯=Sd=W
由于方法可能很多,因此只需要输出最后的答案对 109+7 取模的结果。
输入格式
第一行输入两个正整数 n,k。
第二行输入一个长度为 n 的字符串 S。
输出格式
输出一行,包含一个整数,表示答案
样例输入
5 2
XXXXX
样例输出
4
数据规模与约定
对于 20% 的数据,n≤20。
对于 50% 的数据,n≤2×103。
对于 100% 的数据,n,k≤106。
题目来源
中国国家队清华集训 2012-2013 第一天