题目描述

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

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

• $1\le a\le b<c\le d\le n$。
• $b=a+k-1,d=c+k-1$
• $S_a=S_{a+1}=\cdots=S_{b}=\texttt{B}$
• $S_c=S_{c+1}=\cdots=S_{d}=\texttt{W}$

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

输入格式

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

第二行输入一个长度为 $n$ 的字符串 $S$。

输出格式

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

样例输入

5 2
XXXXX

样例输出

4

数据规模与约定

对于 $20\%$ 的数据，$n\leq 20$。 对于 $50\%$ 的数据，$n\leq 2\times10^3$。 对于 $100\%$ 的数据，$n,k\leq 10^6$。

题目来源

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