问题描述

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

对于给出的 $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$