记录编号	613972	评测结果	AAAAAAAAAA
题目名称	4371.大括号	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	3.071 s
提交时间	2026-04-02 22:00:54	内存使用	234.62 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,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;
}
int main(){
	freopen("brace.in","r",stdin);
	freopen("brace.out","w",stdout);
	scanf("%d %lld %lld %d %d",&n,&p,&q,&a,&b);
	scanf("%s",s+1);
	invL=p*ksm(p+q,mod-2)%mod;
	invR=q*ksm(p+q,mod-2)%mod;
	f[0][a]=1;
	for(int i=0;i<n;i++){
		if(s[i+1]=='R'){
			ll sum=0;
			for(int j=1;j<=n;j++){
				(sum=sum*invR%mod+f[i][j]%mod)%=mod;
				(f[i+1][j]+=sum*invL%mod)%=mod;
			}
		}else{
			for(int j=1;j<=n;j++){
				(f[i+1][j-1]+=f[i][j])%=mod;
			}
		}
	}
	g[n+1][b]=1;
	for(int i=n+1;i>1;i--){
		if(s[i-1]=='L'){
			ll sum=0;
			for(int j=1;j<=n;j++){
				(sum=sum*invL%mod+g[i][j])%=mod;
				(g[i-1][j]+=sum*invR%mod)%=mod;
			}
		}else{
			for(int j=1;j<=n;j++){
				(g[i-1][j-1]+=g[i][j])%=mod;
			}
		}
	}
	if(a==0)ans=g[1][0];
	else if(b==0)ans=f[n][0];
	else{
		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);
	return 0;
}