记录编号	613939	评测结果	WWWWTTTTTT
题目名称	4371.大括号	最终得分	0
用户昵称	RpUtl	是否通过	未通过
代码语言	C++	运行时间	7.313 s
提交时间	2026-04-02 20:15:20	内存使用	6.10 MiB

#include <iostream>
#include <cstdio>
using namespace std;
const int mod=666623333;
const int N=5005;
typedef long long ll;
int n,a,b;
ll p,q,pwL[N],pwR[N],f[N][N],g[N][N],invL,invR,ans;
char s[N];
ll ksm(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
/*
f[i][x] f[i][x-1] 1
f[i][x] f[i][x+y] ((q)/(p+q))^y*(p/(p+q))
*/
int main(){
	freopen("brace.in","r",stdin);
	freopen("brace.out","w",stdout);
	scanf("%d %d %d %d %d",&n,&p,&q,&a,&b);
	scanf("%s",s+1);
	invL=p*ksm(p+q,mod-2)%mod;pwL[0]=1;
	invR=q*ksm(p+q,mod-2)%mod;pwR[0]=1;
	for(int i=1;i<=n;i++){
		pwL[i]=pwL[i-1]*invL%mod;
		pwR[i]=pwR[i-1]*invR%mod;
	}
	f[0][a]=1;
	for(int i=0;i<n;i++){
		if(s[i+1]=='R'){
			for(int j=0;j<=n;j++){
				for(int k=0;k<=n-j;k++){
					f[i+1][j+k]+=pwR[k]*f[i][j]%mod*invL%mod;
					f[i+1][j+k]%=mod;
				}
			}
		}else{
			for(int j=1;j<=n;j++){
				f[i+1][j-1]+=f[i][j];
				f[i+1][j-1]%=mod;
			}
		}
	}
	g[n+1][b]=1;
	for(int i=n+1;i>1;i--){
		if(s[i-1]=='L'){
			for(int j=0;j<=n;j++){
				for(int k=0;k<=n-j;k++){
					g[i-1][j+k]+=pwL[k]*g[i][j]%mod*invR%mod;
					g[i-1][j+k]%=mod;
				}
			}
		}else{
			for(int j=1;j<=n;j++){
				g[i-1][j-1]+=g[i][j];
				g[i-1][j-1]%=mod;
			}
		}
	}
	for(int i=1;i<n;i++){
		if(s[i]=='L'&&s[i+1]=='R'){
			ans+=f[i][0]*g[i+1][0]%mod;
			ans%=mod;
		}
	}
	printf("%lld\n",ans);
}