#include<bits/stdc++.h>
#define N 185
using namespace std;
const int t=90;
int n;
signed int dp[N][N][N][2][2];
char s[N],t0[N],t1[N];
int nxt0[N],nxt1[N];
signed int DP(int x,int y,int z){
	for(int i=0;i<=3*n;i++)
		for(int j=t-i;j<=t+i;j++){
			int pl=max(t-i,max(2*t-j-z,max(i+j-3*n,i-2*j+3*t-3*n)));
			while((3*t+i+j-pl)%3!=0) pl++;
			int pr=min(t+i,min(t+y,(3*n-i+3*t-j)/2));
			for(int k=pl;k<=pr;k+=3)
				for(int x=0;x<2;x++)
					for(int y=0;y<2;y++)
						dp[i][j][k][x][y]=0;
		}
	dp[0][t][t][x==0][y==0]=1;
	for(int i=1;i<=3*n;i++)
		for(int j=t-i;j<=t+i&&j<=t+x;j++){
			int pl=max(t-i,max(2*t-j-z,max(i+j-3*n,i-2*j+3*t-3*n)));
			while((3*t+i+j-pl)%3!=0) pl++;
			int pr=min(t+i,min(t+y,(3*n-i+3*t-j)/2));
			for(int k=pl;k<=pr;k+=3)
				for(int u=0;u<2;u++)
					for(int v=0;v<2;v++){
						int tu=(u|(j==t+x)),tv=(v|(k==t+y));
						signed int &f=dp[i][j][k][tu][tv];
						if(s[i]=='?'||s[i]=='A')
							f+=dp[i-1][j-1][k+1][u][v];
						if(s[i]=='?'||s[i]=='B')
							f+=dp[i-1][j][k-1][u][v];
						if(s[i]=='?'||s[i]=='C')
							f+=dp[i-1][j+1][k][u][v];
					}
		}
	return dp[3*n][t][t][1][1];
}
int main(){
	int t,id;
	scanf("%d%d",&t,&id);
	for(int o=1;o<=t;o++){
		scanf("%d%s%s%s",&n,t0,t1,s+1);
		if(o<t) puts("-1");
	}
	for(int i=0;i<=n;i++) t0[i]=t1[i]='1';
	for(int i=1;i<=3*n;i++) s[i]='?';
	nxt0[n+1]=nxt1[n+1]=1;
	for(int i=n;i>=0;i--){
		nxt0[i]=(t0[i]=='1'?i:nxt0[i+1]);
		nxt1[i]=(t1[i]=='1'?i:nxt1[i+1]);
	}
	signed int ans=0;
	for(int i=0;i<=n;i++)
		for(int j=0;i+j<=n;j++)
			if(nxt0[i]<=n&&nxt1[j]<=n&&nxt0[i]+nxt1[j]<=n)
				ans+=DP(i,j,n-nxt0[i]-nxt1[j]);
	printf("%u\n",ans);
}