P6212 「SWTR-4」Lining up

作为班长的小 S 在指挥操场上的一群同学排队，Lining up 可不是一件容易的事情。

操场上有排成一列的 $n$ 个同学，每个同学要么是男生，用 ```B``` 表示；要么是女生，用 ```G``` 表示。 我们定义两个相邻的同学的满意度如下： - 如果两个相邻的同学的性别相同，那么就会像普通同学一样聊天，产生 $0$ 点满意度。 - 如果前面的同学是男生，后面的同学是女生，那么就不会有任何事件发生。同学们都很活跃，他们不希望这么无聊，产生 $-b$ 点满意度。 - 如果前面的同学是女生，后面的同学是男生，那么他们就会聊得很开心，产生 $a$ 点满意度。 由于小 S 是近视眼，所以他无法分辨有些同学的性别，用 ```?``` 表示。 为了提高自己在大家心目中的地位，小 S 想保证所有相邻同学的满意度之和不小于 $m$。 他想知道满足“所有相邻同学的满意度之和不小于 $m$”的概率是多少，对 $10^9+7$ 取模。

第一行，四个整数 $n,m,a,b$ —— 意义见题目描述。 第二行，一个长度为 $n$ 的字符串 $s$ 表示队列 —— 第 $i$ 个字符表示**从前往后**数第 $i$ 位同学。

一行，表示概率。

【样例 $1$ 说明】 共有 $1$ 个满足题意的队形 $\tt BGB$。概率为 $\frac{1}{2} \bmod (10^9+7)=500000004$。 【样例 $2$ 说明】 共有 $6$ 个满足题意的队形 $\tt BBB,BGB,GBB,GBG,GGB,GGG$。概率为 $\frac{6}{8} \bmod (10^9+7)=750000006$。 【样例 $5$ 说明】 真实答案为 $\dfrac{29}{64}$。 【数据范围与约定】 **本题使用捆绑测试。** Subtask 编号 | $n\leq$ | 特殊性质 | 分数 :-: | :-: | :-: | :-: $1$ | $2020$ | 没有```?``` | $8$ $2$ | $20$ | 无 | $17$ $3$ | $250$ | 无 | $29$ $4$ | $2020$ | $a=1,b=1$ | $10$ $5$ | $2020$ | 无 | $36$ 对于全部数据，$2 \leq n \leq 2020$，$1 \leq |m| \leq 10^{12}$，$1 \leq a,b \leq 10^9$，$s_i \in \tt{\{B,G,?\}}$。 **请注意特殊的空间限制。** 【Tips】 如果你不会对分数取模，可以看看[这里](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)，验题：[Isaunoya](https://www.luogu.com.cn/user/96580) & [FrenkiedeJong21](https://www.luogu.com.cn/user/203968) & [chenxia25](https://www.luogu.com.cn/user/138400)