挺有意思的题。
一开始看到 想的是一个类似区间 dp 的东西，但是没写完就发现这样完全不能去重。
于是考虑推一些性质。一开始序列是 AB，不妨设 ，另一种情况大概是对称的。则序列会变成 AAB。此时发现，右半边仍然是 AB，怎么做都只能再增加一个 A。所以只用考虑左半边的 AA。
同时注意到这要求最终的 。
-
如果 ，那么最终序列就只有
AAA...AB这一种情况。 -
否则若 ，则可以发现，任何一个 的序列都可以构造出来，方法是先不管开头的
A和结尾的B，每次找到最后一个连续段，先把这个连续段的第一个位置填上，再往后填。故方案数为 。 -
否则还是类似上面的，但是此时不能有两个连续的
B，因为 。这是一个经典计数问题，设 为长为 的序列的方案数，则 为 的斐波那契数列。方案数为 。
的答案是类似的，对称地推一下即可。
code：
int n,m,a[4],f[N];
il int Mod(int x,int y){
return x+y>=mod?x+y-mod:x+y;
}
il int qpow(int x,int y){
int ret=1;
while(y){
if(y&1){
ret=1ll*ret*x%mod;
}
x=1ll*x*x%mod,y>>=1;
}
return ret;
}
void Yorushika(){
read(n);
if(n==2){
puts("1");
return;
}
rep(i,0,3){
char s[7];scanf("%s",s);
a[i]=s[0]-'A';
}
f[0]=1,f[1]=2;
rep(i,2,n){
f[i]=Mod(f[i-1],f[i-2]);
}
if(a[1]==0){
if(a[0]==0){
puts("1");
}else{
if(a[2]==1){
printf("%d\n",qpow(2,n-3));
}else{
printf("%d\n",f[n-3]);
}
}
}else{
if(a[3]==1){
puts("1");
}else{
if(a[2]==0){
printf("%d\n",qpow(2,n-3));
}else{
printf("%d\n",f[n-3]);
}
}
}
}
signed main(){
int t=1;
//read(t);
while(t--){
Yorushika();
}
}
