rt，有注释。

不能过样例QWQ .

/*
f[i][j]:前i行状态为j时的方案数
state[]状态,line[i]第i行土地的二进制状态 
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register int 
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f==1?x:-x;
} 
const int mod=1e9;
int n,m,f[12+5][4096+5],state[4096+5],line[4096+5],cnt;
int a[12+5][12+5];
void init()
{
	int tot=(1<<n)-1;
	for(re i=0;i<=tot;++i)
		if(!(i&(i<<1))) state[++cnt]=i;//横向不能相邻 
}
signed main()
{
	n=read(),m=read();
	for(re i=1;i<=n;++i)
		for(re j=1;j<=m;++j)
		{
			a[i][j]=read();
			line[i]=(line[i]<<1)+a[i][j];
		}
	init();
//	for(re i=1;i<=n;++i) printf("%lld\n",line[i]);
	for(re i=1;i<=cnt;++i) 
		if((state[i] & line[1])==state[i]) f[1][i]=1; //初始化第一行 
	for(re i=2;i<=n;++i)
		for(re now=1;now<=cnt;++now)//当前行状态 
		{
			if((state[now] & line[i])!=state[now])continue;//方案不能占用不适合种草的土地 
			for(re lst=1;lst<=cnt;++lst)//上一行状态 
				if(!(state[now] & state[lst]))//纵向不能相邻 
					f[i][now]=(f[i][now]+f[i-1][lst])%mod;//转移 
		} 
	int ans=0;
	for(re i=1;i<=cnt;++i)
		ans=(ans+f[n][i])%mod;
	printf("%lld\n",ans);
	return 0;
}