题目背景

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

题目描述

操场上有排成一列的 $n$ 个同学，每个同学要么是男生，用 B 表示；要么是女生，用 G 表示。

我们定义两个相邻的同学的满意度如下：

• 如果两个相邻的同学的性别相同，那么就会像普通同学一样聊天，产生 $0$ 点满意度。

• 如果前面的同学是男生，后面的同学是女生，那么就不会有任何事件发生。同学们都很活跃，他们不希望这么无聊，产生 $-b$ 点满意度。

• 如果前面的同学是女生，后面的同学是男生，那么他们就会聊得很开心，产生 $a$ 点满意度。

由于小 S 是近视眼，所以他无法分辨有些同学的性别，用 ? 表示。

为了提高自己在大家心目中的地位，小 S 想保证所有相邻同学的满意度之和不小于 $m$。

他想知道满足“所有相邻同学的满意度之和不小于 $m$”的概率是多少，对 $10^9+7$ 取模。

输入格式

第一行，四个整数 $n,m,a,b$ —— 意义见题目描述。

第二行，一个长度为 $n$ 的字符串 $s$ 表示队列 —— 第 $i$ 个字符表示从前往后数第 $i$ 位同学。

输出格式

一行，表示概率。

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

提示

【样例 $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$		无	$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】

如果你不会对分数取模，可以看看这里。

【Source】

Sweet Round 04$\ \$D

idea：ET2006，std：Isaunoya，验题：Isaunoya & FrenkiedeJong21 & chenxia25