题目背景

题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。

题目描述

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

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

• $1\leq a\leq b< c\leq d\leq n$；
• $b=a+k-1$，$d=c+k-1$;
• $S_a=S_{a+1}=\dots=S_b=\tt B$；
• $S_c=S_{c+1}=\dots=S_d=\tt W$；

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

5 2
XXXXX

输出 #1

4

说明/提示

对于 $20\%$ 的数据，$1\leq n\leq 20$；

对于 $50\%$ 的数据，$1\leq n\leq 2000$；

对于 $100\%$ 的数据，$1\leq n,k\leq 10^6$。