Problem Description

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$.

Input Format

The first line contains three integers $N,M,K$.

The second line contains a string $S$ of length $N$.

Output Format

Output one integer representing the answer.

5 4 1
?????

4

5 2 2
A????

6

5 3 4
AAAAA

0

Hint

Sample Explanation

For the first sample, the following are all valid strings:

AAAAB
ABBBB
BAAAA
BBBBA

For the second sample, the following are all valid strings:

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