题解（容斥）

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

typedef unsigned long long ull;

const int P=1e9+7,N=35,B=65536,M=1005,L=105;

int h1,h2;
int n,m,mr,nr[M],ln[M],cnt[B];
int v[L];
char s[L];

int pw2[N],pw3[N];
ull mask[4],msk[B][4];//0:不变;1:变;2:为 0;3:为 1 
ull emp[B],rct[B];//emp:必须为空的位置;rct:有限制的位置 

int nw[B],f0[B];//nw:当前行状态为 S 的方案数;f0:所有行状态为 S 的方案数 
int f1[N][B],f2[N][B];
//f1[i][S]:左半部分从右向左第 i个位置在它后面 i(包含它)个位置被选择的状态为 S时左半部分最右侧的点能够在操作后保持不变的方案数 
//f2[i][S]:左半部分从右向左第 i个位置在它后面 i(包含它)个位置被选择的状态为 S时的总方案数 
int g[2][B];//开个滚动数组，以免爆炸 

inline int exminus(const int &a,const int &b) {int x=a-b;return x<0?x+P:x;}
inline int explus(const int &a,const int &b) {int x=a+b;return x<P?x:x-P;}
inline void Exminus(int &a,const int &b) {if((a-=b)<0) a+=P;}
inline void Explus(int &a,const int &b) {if((a+=b)>=P) a-=P;}
inline int mul2(int a) {Explus(a,a);return a;}
inline int mul3(int a) {Explus(a,mul2(a));return a;}

inline int get(ull S) {return cnt[S>>h1]+cnt[S&((1<<h1)-1)];}

inline int calc(int p) {
	int res=0;
	for(int S=0 ; S<(1<<p) ; ++S) if(S&1)
		if(cnt[S]&1) Explus(res,f2[p][S]); 
		else Exminus(res,f2[p][S]);
	for(int S=0 ; S<(1<<p) ; ++S) g[0][S]=0;
	int t=0,ret=1;g[0][0]=1;
	for(int i=0 ; i<=n-2*p ; ret=1ll*ret*f1[p][0]%P,++i,t^=1)
		for(int S=0 ; S<(1<<p) ; ++S)
			g[t^1][S]=1ll*exminus(g[t][S>>1],g[t][S>>1|(1<<(p-1))])*f1[p][S]%P;
	Exminus(g[t][0],ret);
	for(int i=n-2*p+1 ; i<n-p ; ++i,t^=1)
		for(int S=0 ; S<(1<<p) ; ++S)
			g[t^1][S]=1ll*exminus(g[t][S>>1],g[t][S>>1|(1<<(p-1))])*f1[p][S]%P;
	for(int i=n-p ; i<n ; ++i,t^=1)
		for(int S=0 ; S<(1<<p) ; ++S)
			if((S&1)==(i==n-p)) g[t^1][S]=1ll*exminus(g[t][S>>1],g[t][S>>1|(1<<(p-1))])*f1[p][S]%P;
			else g[t^1][S]=0;
	for(int S=0 ; S<(1<<p) ; ++S)
		if(cnt[S]&1) Explus(res,g[t][S]);
		else Exminus(res,g[t][S]);
	return res;
}

int main() {
	freopen("robot.in","r",stdin);
	freopen("robot.out","w",stdout);
	scanf("%d%d",&n,&m);
	h1=(n+1)>>1,h2=n-h1;
	for(int S=0 ; S<(1<<h1) ; ++S) cnt[S]=cnt[S>>1]+(S&1);
	for(int S=0 ; S<(1<<h1) ; ++S) f0[S]=1;
	for(int i=1 ; i<=h2 ; ++i)
		for(int S=0 ; S<(1<<i) ; ++S)
			f1[i][S]=f2[i][S]=1;
	pw2[0]=pw3[0]=1;
	for(int i=1 ; i<=n ; ++i) pw2[i]=mul2(pw2[i-1]),pw3[i]=mul3(pw3[i-1]);
	for(int o=0 ; o<m ; ++o) {
		scanf("%s",s);
		int len=strlen(s),p=0;
		v[0]=0;
		for(int i=0 ; i<len ; ++i)
			if(s[i]=='R') v[++p]=0;
			else if(s[i]=='0') v[p]=2;
			else if(s[i]=='1') v[p]=3;
			else v[p]^=1;
		if((++p)>n) continue ;
		for(int i=0 ; i<4 ; ++i) mask[i]=0;
		for(int i=0 ; i<p ; ++i) mask[v[i]]|=1ull<<i;
		int l=min(h1,n-p+1);
		for(int S=0 ; S<(1<<l) ; ++S)
			for(int i=0 ; i<4 ; ++i)
				msk[S][i]=0;
		for(int i=0 ; i<l ; ++i) {
			for(int j=0 ; j<4 ; ++j) msk[1<<i][j]=mask[j]<<(l-1-i);
			msk[1<<i][0]|=(1ull<<(l-1-i))-1;
			msk[1<<i][0]|=(1ull<<n)-(1ull<<(l-1-i+p));
		}
		for(int S=0 ; S<(1<<l) ; ++S)
			for(int j=0 ; j<4 ; ++j)
				msk[S][j]=msk[S^(S&-S)][j]|msk[S&-S][j];
		for(int S=0 ; S<(1<<l) ; ++S) {
			emp[S]=(msk[S][0]&msk[S][1])|(msk[S][2]&msk[S][3]);
			rct[S]=(msk[S][0]|msk[S][1])&(msk[S][2]|msk[S][3]);
			rct[S]|=emp[S];
			int c1=get(emp[S]),c2=get(rct[S]);
			nw[S]=1ll*pw3[n-c2]*pw2[c2-c1]%P,f0[S]=1ll*f0[S]*nw[S]%P;
		}
		if(p>h2) continue ;
		for(int i=p ; i<=h2 ; ++i)
			for(int S=0 ; S<(1<<i) ; ++S)
				f2[i][S]=1ll*f2[i][S]*nw[S]%P;
		for(int S=0 ; S<(1<<h2) ; ++S) {
			emp[S]|=msk[S][1];
			rct[S]|=msk[S][1]|msk[S][2]|msk[S][3];
			nw[S]=3-(rct[S]>>(h1-1)&1)-(emp[S]>>(h1-1)&1);
		}
		for(int i=p ; i<=h2 ; ++i)
			for(int S=0 ; S<(1<<i) ; ++S)
				f1[i][S]=1ll*f1[i][S]*nw[S]%P;
	}
	int res=0;
	for(int S=1 ; S<(1<<h1) ; ++S)
		if(cnt[S]&1) Explus(res,f0[S]);
		else Exminus(res,f0[S]);
	for(int i=1 ; i<=h2 ; ++i) Explus(res,calc(i));
	printf("%d",res);
	return 0;
}