#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++)
			for(int k=t-i;k<=t+i;k++)
				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++)
			for(int k=t-i;k<=t+i&&k<=t+y;k++){
				int l=t*3-j-k;
				if(l>t+z||i+j-k>3*n||i+k-l>3*n||i+l-j>3*n) continue;
				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");
	}
	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("%d\n",ans);
}