记录编号	614207	评测结果	AAAAAAAAAA
题目名称	4371.大括号	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	1.720 s
提交时间	2026-04-07 15:17:47	内存使用	119.40 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3;
const int P = 666623333;
int power(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % P)
        if (b & 1)
            res = 1ll * res * a % P;
    return res;
}
int f[N + 1][N + 1], g[N + 1][N + 1];
int main() {
	freopen("brace.in", "r", stdin);
	freopen("brace.out", "w", stdout);
    int n, r, h, b, a;
    cin >> n >> r >> h >> b >> a;
    string s;
    cin >> s;
    int v = r + h;
    v = power(v, P - 2) % P;
    r = 1ll * r * v % P;
    h = 1ll * h * v % P;
    f[0][b] = 1;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'L') {
            std::copy(f[i] + 1, f[i] + n + 1, f[i + 1]);
        } else {
            for (int j = 1; j <= n; ++j)
                f[i + 1][j] = (1ll * f[i + 1][j - 1] * h + 1ll * f[i][j] * r) % P;
        }
    }
    g[n][a] = 1;
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] == 'R') {
            std::copy(g[i + 1] + 1, g[i + 1] + n + 1, g[i]);
        } else {
            for (int j = 1; j <= n; ++j)
                g[i][j] = (1ll * g[i][j - 1] * r + 1ll * g[i + 1][j] * h) % P;
        }
    }
    int ans = 0;
    for (int i = 0; i <= n; ++i)
        ans = (ans + 1ll * f[i][0] * g[i][0]) % P;
    std::cout << ans << "\n";
    return 0;
}