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.


Submitting to 'Self Defence'


You're not logged in! Click here to login


Submitting to 'Self Defence'


You're not logged in! Click here to login


Submitting .cpp to 'Self Defence'


You're not logged in! Click here to login

Time Limit: 3 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: TOKI KSN Day 1

Subtask Score
1 5
2 9
3 11
4 6
5 9
6 8
7 27
8 25
9 0