P6212 "SWTR-4" Lining up

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.

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$.

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 one line containing the probability.

[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.** Subtask ID | $n\leq$ | Special property | Score :-: | :-: | :-: | :-: $1$ | $2020$ | No ```?``` | $8$ $2$ | $20$ | None | $17$ $3$ | $250$ | None | $29$ $4$ | $2020$ | $a=1,b=1$ | $10$ $5$ | $2020$ | None | $36$ 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](https://www.luogu.com.cn/problem/P2613). [Source] [Sweet Round 04](https://www.luogu.com.cn/contest/26414)$\ \ $D idea: [ET2006](https://www.luogu.com.cn/user/115194), std: [Isaunoya](https://www.luogu.com.cn/user/96580), validator: [Isaunoya](https://www.luogu.com.cn/user/96580) & [FrenkiedeJong21](https://www.luogu.com.cn/user/203968) & [chenxia25](https://www.luogu.com.cn/user/138400) Translated by ChatGPT 5