UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2958. 序列染色

Statistics 下载数据

Description

  给出一个长度为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取模的结果。

Input

  第一行两个正整数N,K
  第二行一个长度为N的字符串S

Output


  一行一个整数表示答案%(109+7)。

Sample Input


5 2
XXXXX

Sample Output


4
数据约定
  对于20%的数据,N<=20
  对于50%的数据,N<=2000
  对于100%的数据,1<=N<=10^6,1<=K<=10^6

Hint

Source

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