P7969 [KSN2021] Self Defence

Define the weight of a string as the number of its substrings that have length $M$ and contain only one distinct character. For example, for the string ``ABBB``, when $M=2$, its weight is $2$. Given a string of length $N$, where each character is one of ``?``, ``A``, and ``B``, you need to find how many strings can be obtained with weight $K$ after replacing each ``?`` with ``A`` or ``B``. Output the answer modulo $10^9+7$.

The first line contains three integers $N,M,K$. The second line contains a string $S$ of length $N$.

Output one integer representing the answer.

**Sample Explanation** For the first sample, the following are all valid strings: ```plain AAAAB ABBBB BAAAA BBBBA ``` For the second sample, the following are all valid strings: ```plain AAABA AABAA AABBA ABAAA ABBAA ABBBA ``` **Constraints** **This problem uses bundled testdata.** * Subtask 1 (5 points): There is only one test case, satisfying $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$ contains only ``?``. * Subtask 8 (25 points): No special restrictions. For all test cases, $1\leq N\leq 3000$, $1\leq M\leq N$, $0\leq K\leq N$. Translated by ChatGPT 5