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.
A
, B
, or ?
.????A???B?
.?
.The input is given with the following format:
N M K S_{1}S_{2}…S_{N}
5 4 1 ?????
4
In this sample, the potent prescriptions are:
AAAAB ABBBB BAAAA BBBBA
5 2 2 A????
6
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
In this sample, the only prescription which conforms with Pak Dengklek's plan is not potent.
Subtask | Score |
---|---|
1 | 5 |
2 | 9 |
3 | 11 |
4 | 6 |
5 | 9 |
6 | 8 |
7 | 27 |
8 | 25 |
9 | 0 |