String Weight Count

Given a string of length N consisting of characters 'A', 'B', and '?' where each '?' can be replaced by either 'A' or 'B'. Define the weight of a string as the number of substrings of length \(M\) that contain exactly one distinct character, i.e. they are composed of the same letter. For example, for the string ABBB with \(M=2\), its substrings of length 2 are AB, BB, and BB; among these, BB and BB are uniform, so the weight is 2.

You are also given an integer \(K\). Your task is to count, modulo \(10^9+7\), the number of ways to replace every '?' with either 'A' or 'B' so that the resulting string has weight exactly \(K\>.

inputFormat

The input consists of two lines. The first line contains three integers \(N\), \(M\), and \(K\) separated by spaces. The second line contains a string of length \(N\) consisting only of the characters '?', 'A', and 'B'.

outputFormat

Output a single integer, the number of valid replacements that result in the string having weight exactly \(K\), modulo \(10^9+7\).

sample

4 2 2
ABBB

1