题目描述

给出一个长度为 $N$ 由 $\text B,\text W,\text X$ 三种字符组成的字符串 $S$，你需要把每一个 $\text X$ 染成 $\text B$ 或 $\text W$ 中的一个。 对于给出的 $K$，问有多少种染色方式使得存在整数 $a,b,c,d$ 使得 $1\leq a\leq b<c\leq d\leq N$ 且 $S_a,S_{a+1},...,S_b$ 均为 $\text B$，$S_c,S_{c+1},...,S_d$ 均为 $\text W$，其中 $b=a+K-1$，$d=c+K-1$。由于方法可能很多，因此只需要输出最后的答案对 $10^9+7$ 取模的结果。

输入格式

第一行两个正整数 $N,K$，第二行一个长度为 $N$ 的字符串 $S$。

输出格式

一行一个整数表示答案模 $10^9+7$ 的结果。

5 2
XXXXX

4

数据规模与约定

对于 $100\%$ 的数据，满足 $1\leq N\leq 10^6$，$1\leq K\leq 10^6$。

题目来源

DP