#P2958. 序列染色

    ID: 2078 传统题 1000ms 512MiB 尝试: 591 已通过: 269 难度: 7 上传者: 标签>CF2200提高计数 DP前后缀状态分解补集计数加法原理中国国家队清华集训2012-2013第一天

序列染色

题目描述

给出一个长度为 nn,由 B\texttt{B},W\texttt{W},X\texttt{X} 三种字符组成的字符串 SS,你需要把每一个 X\texttt{X} 染成 B\texttt{B} 或 W\texttt{W} 中的一个。

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

  • 1≤a≤b<c≤d≤n1\le a\le b<c\le d\le n。
  • b=a+k−1,d=c+k−1b=a+k-1,d=c+k-1
  • Sa=Sa+1=⋯=Sb=BS_a=S_{a+1}=\cdots=S_{b}=\texttt{B}
  • Sc=Sc+1=⋯=Sd=WS_c=S_{c+1}=\cdots=S_{d}=\texttt{W}

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

输入格式

第一行输入两个正整数 n,kn,k。

第二行输入一个长度为 nn 的字符串 SS。

输出格式

输出一行,包含一个整数,表示答案

样例输入

5 2
XXXXX

样例输出

4

数据规模与约定

对于 20%20\% 的数据,n≤20n\leq 20。 对于 50%50\% 的数据,n≤2×103n\leq 2\times10^3。 对于 100%100\% 的数据,n,k≤106n,k\leq 10^6。

题目来源

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