Problem Description

Define the weight of a string as the number of its substrings of length $M$ that consist of a single character.

For example, the string "ABBB" has a weight of $2$ when $M=2$.

Given a string of length $N$ where each character is either ?, A, or B, you need to determine how many ways you can replace each ? with either A or B to obtain a string with a weight of $K$.

The answer should be taken 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 a single integer representing the answer.

Sample Input and Output

Sample Input #1

5 4 1
?????

Sample Output #1

4

Sample Input #2

5 2 2
A????

Sample Output #2

6

Sample Input #3

5 3 4
AAAAA

Sample Output #3

0

Notes

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

Data Range

This problem uses batched testing.

• Subtask 1 (5 points): Only one set of data exists, satisfying $N=10$, $M=3$, $K=5$, $S=\texttt{????A???B?}$.
• Subtask 2 (9 points): $N \leq 20$.
• Subtask 3 (11 points): $N \leq 200$.
• Subtask 4 (6 points): $M=2$, $K=0$.
• Subtask 5 (9 points): $K=0$.
• Subtask 6 (8 points): $K \leq 1$.
• Subtask 7 (27 points): $S$ consists only of ?.
• Subtask 8 (25 points): No special restrictions.

For all data, $1 \leq N \leq 3000$, $1 \leq M \leq N$, $0 \leq K \leq N$.

见题面 Input 部分

见题面 Output 部分