序列染色

题目描述

　　给出一个长度为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
数据约定
　　对于20%的数据，N<=20
　　对于50%的数据，N<=2000
　　对于100%的数据，1<=N<=10^6，1<=K<=10^6

---

提示

没有写明提示

---

题目来源

　中国国家队清华集训 2012-2013 第一天