P7969 [KSN2021] Self Defence

定义一个字符串的权值为它长度为 $M$ 且只包含一种字符的子串数量。 例如字符串 ``ABBB``，在 $M=2$ 时的权值为 $2$。 给定一个长度为 $N$ 的字符串，每个字符为 ``?``，``A`` 和 ``B`` 中的一个，你需要求出将每个 ``?`` 替换为 ``A`` 或 ``B`` 后，可以得到多少个权值为 $K$ 的字符串。 答案对 $10^9+7$ 取模。

第一行输入三个整数 $N,M,K$。 第二行输入一个长度为 $N$ 的字符串 $S$。

输出一个整数代表答案。

**【样例解释】** 对于第一组样例，以下为所有合法字符串： ```plain AAAAB ABBBB BAAAA BBBBA ``` 对于第二组样例，以下为所有合法字符串： ```plain 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$。