Background

As the class monitor, Little S is directing a group of classmates to line up on the playground. Lining up is not an easy task.

Problem Description

There are $n$ students standing in a single line on the playground. Each student is either a boy, denoted by B, or a girl, denoted by G.

We define the satisfaction of two adjacent students as follows:

• If the two adjacent students have the same gender, then they chat like ordinary classmates, producing $0$ satisfaction.

• If the student in front is a boy and the one behind is a girl, then nothing happens. The students are very active and do not want it to be so boring, producing $-b$ satisfaction.

• If the student in front is a girl and the one behind is a boy, then they chat very happily, producing $a$ satisfaction.

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

To improve his status in everyone’s eyes, Little S wants to ensure that the sum of satisfaction over all adjacent pairs is at least $m$.

He wants to know the probability that the condition “the sum of satisfaction over all adjacent pairs is at least $m$” holds, modulo $10^9+7$.

Input Format

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

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

Output Format

Output one line containing the probability.

3 1 2 1
BG?

500000004

3 -1 4 3
???

750000006

5 5 7 3
G??B?

625000005

6 10 9 4
??GB??

937500007

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

78125001

Hint

[Sample $1$ Explanation]

There is $1$ lineup that satisfies the condition: $\tt BGB$. The probability is $\frac{1}{2} \bmod (10^9+7)=500000004$.

[Sample $2$ Explanation]

There are $6$ lineups that satisfy the condition: $\tt BBB,BGB,GBB,GBG,GGB,GGG$. The probability is $\frac{6}{8} \bmod (10^9+7)=750000006$.

[Sample $5$ Explanation]

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

[Constraints and Notes]

This problem uses bundled testdata.

For all testdata: $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 memory limit.

[Tips]

If you do not know how to take a fraction modulo, you can read here.

[Source]

Sweet Round 04$\ \$D

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

Translated by ChatGPT 5