题目描述

定义一个字符串的权值为它长度为 $M$ 且只包含一种字符的子串数量。

例如字符串 ABBB，在 $M=2$ 时的权值为 $2$。

给定一个长度为 $N$ 的字符串，每个字符为 ?，A 和 B 中的一个，你需要求出将每个 ? 替换为 A 或 B 后，可以得到多少个权值为 $K$ 的字符串。

答案对 $10^9+7$ 取模。

输入格式

第一行输入三个整数 $N,M,K$。

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

输出格式

输出一个整数代表答案。

5 4 1
?????

4

5 2 2
A????

6

5 3 4
AAAAA

0

提示

【样例解释】

对于第一组样例，以下为所有合法字符串：

AAAAB
ABBBB
BAAAA
BBBBA

对于第二组样例，以下为所有合法字符串：

AAABA
AABAA
AABBA
ABAAA
ABBAA
ABBBA

【数据范围】

本题采用捆绑测试。

• Subtask 1（5 points）：只存在一组数据，满足 $N=10$，$M=3$，$K=5$，$S=\texttt{????A???B?}$。
• Subtask 2（9 points）：$N\le 20$。
• Subtask 3（11 points）：$N\le 200$。
• Subtask 4（6 points）：$M=2$，$K=0$。
• Subtask 5（9 points）：$K=0$。
• Subtask 6（8 points）：$K\le 1$。
• Subtask 7（27 points）：$S$ 只包含 ?.
• Subtask 8（25 points）：无特殊限制。

对于所有数据，$1\leq N\leq 3000$，$1\leq M\leq N$，$0\leq K\leq N$。