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.
The input is given with the following format:
N M K S1S2…SN
5 4 1 ?????
In this sample, the potent prescriptions are:
AAAAB ABBBB BAAAA BBBBA
5 2 2 A????
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
In this sample, the only prescription which conforms with Pak Dengklek's plan is not potent.