Self Defence

Description

The country of Toki is plagued by disease! Pak Dengklek, a renowned doctor, is concocting a vitamin prescription to be self-consumed by people at home.

Pak Dengklek's prescription requires a daily intake of one vitamin, either vitamin A or vitamin B, for the next N days. To simplify, Pak Dengklek's prescription plan can be represented as a string S with N characters. The i-th character is either one of:

• A: if vitamin A must be consumed on the i-th day;
• B: if vitamin B must be consumed on the i-th day; or
• ?: if Pak Dengklek has yet to determine which vitamin to be consumed on the i-th day.

Every day, if for the past M days the vitamin type consumed are the same, then the immunity level increased by 1 unit. As an example, if M = 2 and S =BAAA, then Pak Dengklek's immunity will increase by 1 unit on the third day, and increase by another 1 unit on the fourth day.

A prescription is said to be potent if the prescription can increase the immunity level by exactly K units (no less and no more).

Pak Dengklek wants to know the number of different potent prescriptions after Pak Dengklek completed his prescription plan. Count the number modulo 1000000007.

Constraints

• 1 ≤ N ≤ 3000
• 1 ≤ M ≤ N
• 0 ≤ K ≤ N
• Each character of S is either one of A, B, or ?.

Subtasks

1.   (5 points) Contains only the following test case:
   N = 10, M = 3, K = 5, S = ????A???B?.
2.   (9 points) N ≤ 20
3. (11 points) N ≤ 200
4.   (6 points) M = 2, K = 0
5.   (9 points) K = 0
6.   (8 points) K ≤ 1
7. (27 points) All characters of S are ?.
8. (25 points) No additional constraints.

Input

The input is given with the following format:

N M K
S1S2…SN

Output

An integer representing the number of ways to complete the potent prescriptions modulo 1000000007.

Sample Input 1

5 4 1
?????

Sample Output 1

4

Explanation of Sample 1

In this sample, the potent prescriptions are:

AAAAB
ABBBB
BAAAA
BBBBA

Sample Input 2

5 2 2
A????

Sample Output 2

6

Explanation of Sample 2

In this sample, vitamin A must be consumed on the first day. The potent prescriptions which use vitamin A on the first day are:

AAABA
AABAA
AABBA
ABAAA
ABBAA
ABBBA

Sample Input 3

5 3 4
AAAAA

Sample Output 3

0

Explanation of Sample 3

In this sample, the only prescription which conforms with Pak Dengklek's plan is not potent.