Problem Background

As the class monitor, Little S is directing a group of students in a line on the playground, which is not an easy task.

Problem Description

There are $n$ students lined up in a row on the playground. Each student is either a boy, represented by B, or a girl, represented by G.

We define the satisfaction level of two adjacent students as follows:

• If the two adjacent students are of the same gender, they will chat like ordinary classmates, resulting in $0$ points of satisfaction.
• If the student in front is a boy and the student behind is a girl, nothing will happen. The students are lively and do not want to be bored, resulting in $-b$ points of satisfaction.
• If the student in front is a girl and the student behind is a boy, they will chat happily, resulting in $a$ points of satisfaction.

Since Little S is nearsighted, he cannot distinguish the gender of some students, represented by ?.

To enhance his status in the eyes of everyone, Little S wants to ensure that the sum of satisfaction levels of all adjacent students is not less than $m$.

He wants to know the probability that the sum of satisfaction levels of all adjacent students is not less than $m$, modulo $10^9+7$.

Input Format

The first line contains four integers $n, m, a, b$ — as described in the problem statement.

The second line contains a string $s$ of length $n$ representing the queue — the $i$-th character represents the $i$-th student from the front.

Output Format

A single line representing the probability.

Sample Input and Output

Input Sample #1

3 1 2 1
BG?

Output Sample #1

500000004

Input Sample #2

3 -1 4 3
???

Output Sample #2

750000006

Input Sample #3

5 5 7 3
G??B?

Output Sample #3

625000005

Input Sample #4

6 10 9 4
??GB??

Output Sample #4

937500007

Input Sample #5

20 20 15 10
B?G?B?G?????BBBG?GG?

Output Sample #5

78125001

Notes

Sample 1 Explanation

There is $1$ valid formation $\tt$. The probability is $\frac{1}{2} \bmod (10^9+7) = 500000004$.

Sample 2 Explanation

There are $6$ valid formations $\tt$. The probability is $\frac{6}{8} \bmod (10^9+7) = 750000006$.

Sample 5 Explanation

The actual answer is $\dfrac{29}{64}$.

Data Range and Constraints

This problem uses subtask testing.

For all data, $2 \leq n \leq 2020$, $1 \leq |m| \leq 10^{12}$, $1 \leq a, b \leq 10^9$, $s_i \in \tt{\{B, G, ?\}}$.

Please note the special space limits.

Tips

If you do not know how to take the modulo of a fraction, you can refer to this problem.

Source

Sweet Round 04 $ $D

idea: ET2006, std: Isaunoya, tester: Isaunoya & FrenkiedeJong21 & chenxia25

见题面 Input 部分

见题面 Output 部分