#PQJ135x3680. QOJ 135_3680
QOJ 135_3680
标题: 序列染色 - Problem - QOJ.ac
#3680. 序列染色
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