序列染色
时间限制：10s 空间限制：128MB
题目描述
给出一个长度为N由B、W、X三种字符组成的字符串S，你需要把每一个X染成B或W中的一个。
对于给出的K，问有多少种染色方式使得存在整数a,b,c,d使得:
1<=a<=b<c<=d<=N
Sa,Sa+1,...,Sb均为B
Sc,Sc+1,...,Sd均为W
其中b=a+K-1,d=c+K-1
由于方法可能很多，因此只需要输出最后的答案对109+7取模的结果。
输入格式
第一行两个正整数N,K
第二行一个长度为N的字符串S
输出格式
一行一个整数表示答案%(109+7)。
样例输入
5 2 XXXXX
样例输出
4
提示
对于100%的数据，1<=N<=106，1<=K<=106
题目来源
Dp