RT，结构体里的cnt和函数里的cnt没啥用，忽略就好，写代码的时候脑抽加的

#include<iostream>
using namespace std;
int m,n,l;
int Map[20][20];
struct Node{
	long long stt,cnt;
}s[1020];
void dfs(int pos,int cnt,int state){
	if(pos>=m){
		s[++l].stt=state;s[l].cnt=cnt;
		return;
	}
	dfs(pos+1,cnt,state);
	dfs(pos+2,cnt+1,state+(1<<pos));
}
long long f[20][1200];
bool check(int line,long long st){
	for(int i=1; i<=m; i++){
		if(st&1==1 && Map[line][i]==0){ return false;}
		st=(st>>1);
	}
	return true;
}
int main(){
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin>>Map[i][j];
		}
	}
	dfs(0,0,0);
	//f[0][0]=1;
	for(int i=1; i<=l; i++){
		f[1][i]=1;
	}
//	for(int i=1; i<=l; i++){
//		cout<<s[i].cnt<<" "<<s[i].stt<<endl;
//	}
	for(int i=2; i<=n; i++){
		for(int j=1; j<=l; j++){//本行 
			for(int k=1; k<=l; k++){
				if(s[j].stt&s[k].stt) continue;
				if(check(i,s[j].stt)){
			        f[i][j]=(f[i][j]+f[i-1][k])%1000000000;
			    }
			}
		}
	}
	long long ans=0;
	for(int i=1; i<=l; i++){
		ans=(ans+f[n][i])%1000000000;
	}
	cout<<ans<<endl;
}