说是dp感觉是很暴力，关键在于用了二进制来记录每一行的情况
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#define mem(a,x) memset(a,x,sizeof(a))
#define s1(x) scanf("%d",&x)
#define s2(x,y) scanf("%d%d",&x,&y)
#define s3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define s4(x,y,z,k) scanf("%d%d%d%d",&x,&y,&z,&k)
#define ff(a,n) for(int i = 0 ; i < n; i++) scanf("%d",a+i)
#define tp(x) printf("x = %d\n",x)
#define ansp(x) printf("%d\n",x)
#define ls 2*rt
#define rs 2*rt+1
#define lson ls,L,mid
#define rson rs,mid+1,R
#define ll long long
using namespace std;
typedef pair<int,int> pii;
const ll inf = 0x3f3f3f3f;const int mx = 1e9;
int m,n,tol,te;
int dp[13][1<<13];
int cnt[13],sta[1<<13];
bool ok(int x){if(x & x<<1)return 0;return 1;
}
void init(){int te = 1 << n;tol = 0;for(int i = 0; i < te; i++){ //te错写 if(ok(i)){sta[tol++] = i;}}
}bool judge(int x, int k){if(x&cnt[k])return 0;return 1;
}int main(){//int T=10; scanf("%d",&T);// freopen("F:\\in.txt","r",stdin);while(s2(m,n) != EOF){init();mem(dp,0);for(int i = 1; i <= m; i++){cnt[i] = 0;for(int j = 1; j <= n; j++){s1(te);if(te == 0){cnt[i] += (1<<(n-j));}}}for(int i = 0; i < tol; i++){if(judge(sta[i],1))dp[1][i] = 1;}for(int i = 2; i <= m; i++){for(int j = 0; j < tol; j++){if(!judge(sta[j],i))continue;for(int k = 0; k < tol; k++){if(!judge(sta[k],i-1))continue;if((sta[j]&sta[k]) == 0)dp[i][j] = (dp[i][j] + dp[i-1][k])%mx;}}}int ans = 0;for(int i = 0; i < tol; i++){ans = (ans+dp[m][i])%mx;}cout<<ans<<endl;}return 0;
}