#1769. 序列染色

    ID: 1769 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest135来源:qoj.ac数据:公开样例枚举

序列染色

序列染色

题目描述

标题: 序列染色 - 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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 2
XXXXX
4