Satisfaction on the Playground

In a playground, there are (n) students standing in a row. Each student is either a boy denoted by B or a girl denoted by G. However, due to poor eyesight, some students are not clearly identified and are represented by ?.

For any two adjacent students, the satisfaction score is defined as follows:

1. If the two students have the same gender, they chat normally and produce (0) points.
2. If a boy is immediately followed by a girl, nothing exciting happens, and because the students are energetic and do not like being bored, they produce (-b) points.
3. If a girl is immediately followed by a boy, they chat happily and produce (a) points.

Given the string of students and integers (a), (b), and (m), determine the probability that the total satisfaction score over all adjacent pairs is at least (m) after replacing every ? with either B or G arbitrarily. Since each ? is replaced independently, the total number of assignments is (2^{q}), where (q) is the number of question marks. Output the probability modulo (10^9+7) as (\frac{\text{favorable}}{2^q} \bmod (10^9+7)).

inputFormat

The first line contains four integers (n), (a), (b), and (m) separated by spaces. The second line contains a string of length (n) consisting of characters B, G, and ?.

outputFormat

Output a single integer representing the probability that the total satisfaction score is at least (m) modulo (10^9+7).

sample

4 3 2 0
B?GB

1