题目描述
数轴上有 n+1个点，从 0 开始编号。初始在每个i 和i+1 两点之间有一条长度为 1 的边。
每个点可以被划分为两个类别，A 类和 B 类，特殊地，第 0 个点和第 n个点同时属于两类。
每个编号相邻的同类点都会连一条长度为 1 的新边。
有一些点的分类已经确定，有一些没有确定，你需要求出有多少种分类方案满足最后图中1 到 n的距离
不超过 k，对 $10^9+7$取模。
输入格式
第一行两个整数 n和 k。
第二行一个长 n-1的字符串c1...n-1。
$c_i$可能有三种可能字符。若$c_i=A$ ，表示第i 个点确定为 A 类；若 $c_i=B$，表示第 i个点确定为 B 类； 若$c_i=?$ ，表示第i 个点不确定。
输出格式
一个整数，表示答案。
样例
样例输入 #1
8 3 A??AB?B样例输出 #1
4样例输入 #2
16 5 ?A?B?A?B?A?B?A?样例输出 #2
10提示
样例 1 解释：
共有8种分配方案，其中4种合法
1. AAAABAB 0->5->7->8
2. AAAABBB 0->5->4->8
3. AABABAB 无
4. AABABBB 0->3->4->8
5. ABAABAB 无
6. ABAABBB 无
7. ABBABAB 无
8. ABBABBB 0->1->4->8
对于 100%的数据$1<+n<=4000,1<+k<=\frac{n+1}{2}$ 。
Subtask 1（15 pts）:n<=20
Subtask 2（25 pts）：n<=50
Subtask 3（30 pts）：n<=400
Subtask 4（30 pts）：无特殊限制。