#PQJ135x3680. QOJ 135_3680

    ID: 2595 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2012枚举

QOJ 135_3680

标题: 序列染色 - Problem - QOJ.ac

#3680. 序列染色

Statistics

The problem was used in the following contests:

问题描述

给出一个长度为 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≤106,1≤K≤106