QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 3680. 序列染色

Statistics

问题描述

给出一个长度为 $N$ 由 BWX 三种字符组成的字符串 $S$,你需要把每一个 $X$ 染成 BW 中的一个。

对于给出的 $K$,问有多少种染色方式使得存在整数 $a,b,c,d$ 使得:

  • $ 1 \leq a \leq b < c \leq d \leq N$
  • $S_a,S_{a+1},\cdots,S_b$ 均为 B
  • $S_c,S_{c+1}, \cdots ,S_d$ 均为 W

其中 $b=a+K-1$, $d=c+K-1$

由于方法可能很多,因此只需要输出最后的答案对 $10^9+7$ 取模的结果。

输入格式

第一行两个正整数 $N,K$

第二行一个长度为 $N$ 的字符串 $S$

输出格式

一行一个整数表示答案取模 ($10^9+7$)。

样例输入

5 2
XXXXX

样例输出

4

数据约定

对于 $20\%$ 的数据,$N \leq 20$

对于 $50\%$ 的数据,$N \leq 2\,000$

对于 $100\%$ 的数据,$1 \leq N \leq 10^6$,$1 \leq K \leq 10^6$