### 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 `?`.

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.

```5 4 1
?????
```

```4
```

### Explanation of Sample 1

In this sample, the potent prescriptions are:

```AAAAB
ABBBB
BAAAA
BBBBA
```

```5 2 2
A????
```

```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
```

```5 3 4
AAAAA
```

```0
```

### Explanation of Sample 3

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

### Submitting .cpp to 'Self Defence'

Time Limit: 3 Seconds
Memory Limit: 1024MB