T664869 粒子对撞

小L 在一个横向加速器里从左到右依次放置了 n 个粒子,第 z 个粒子被设置成向左或者向右发射。 当两个粒子相撞时,有 $\frac{x}{y}$ 的概率左边的粒子被撞碎,有 $1-\frac{x}{y}$ 的概率右边的粒子被撞碎,剩下的那个粒子会沿着原方向继续移动。 设最终有 a 个粒子从加速器左端射出,有 b 个粒子从加速器右端射出的概率为 $p_{a, b}$ , 请求出下面式子的值: $$\sum_{a=0}^{n} \sum_{b=0}^{n} p_{a, b} f_{a} g_{b}$$ 其中 $f,g$ 是两个输入的数组。 请求出该值对 $10^9+7$ 取模的结果。

第一行三个整数 $n，x，y$ 。 第二行 $n+1$ 个整数代表 $f_{0}, f_{1}, ... f_{n}$ 。 第三行 $n+1$ 个整数代表 $g_{0}, g_{1}, ... g_{n}$ 。 第四行一个长度为 $n$ 的,只包含$L$ 和$R$ 的字符串,分别代表第$i$ 个粒子被设置成向左还是向右。

一个整数代表要求的值。

## 样例1解释 有三种情况: - 只有粒子3 从左边射出,概率为 $p_{1,0}=\frac{1}{4}$ 。 - 只有粒子1 从右边射出,概率为 $p_{0,1}=\frac{1}{4}$ 。 - 粒子1, 2 都从右边射出,概率为 $p_{0,2}=\frac{1}{2}$ 。 因此答案为 $p_{1,0} ×0 ×1+p_{0,1} ×1 ×1+p_{0,2} ×1 ×0=\frac{1}{4} \equiv 250000002(\bmod 10^{9}+7)$ 。 ## 数据范围 - 对于15% 的数据, $n ≤10$ 。 - 对于30% 的数据, $n ≤20$ 。 - 对于45% 的数据, $n ≤50$ 。 - 对于60% 的数据, $n ≤800$ 。 - 对于另外20% 的数据, $s_{i}$ 里$R$ 构成了一个前缀。 - 对于100% 的数据, $1 ≤n ≤5000$ , $0 ≤f_{i}$ , $g_{i} ≤10^{8}$ , $1 ≤x ≤y ≤10^{8}$ 。