#include <iostream>
#include <cstdio>
using namespace std;
namespace wzl{
int m,n;
int a[15] = {},sta[400]={},sit[400]={},cnt=0,f[14][5001]={};
const int p = 1e9 ;
void dfs(int x,int num,int cur){
    if(cur >= n){
        sit[++cnt] = x;
        sta[cnt] = num;
        return ;
    }
    dfs(x,num,cur+1);
    dfs(x+(1<<cur),num+1,cur+2);

}
bool check(int x,int y){
    if(sit[x] & sit[y] ) return false;
    x = sit[x]; y = sit[y];
    int  sm = (x&y);
    if(x - sm > 0) return false;
    return true;
    
}
void main(){
    cin>>m>>n;
    for(int i = 1; i <= m; ++i){
        int x = 1;
        for(int j = 1; j <= n; ++j){
            int ent=0;
            cin>>ent;
            a[i] += ent*x;
            x = (x<<1);
        }
    }
    
    dfs(0,0,0);
    for(int i = 1; i <= cnt; ++i)  f[1][i] = 1;

    for(int i = 2; i <= m; ++i){
        for(int  j = 1; j <= cnt; ++j){
            for(int x = 1; x <= cnt; ++x){
                if(!check(j,x))  continue;
                f[i][j] = (f[i][j]%p + f[i-1][x]%p)%p;
                printf("f[%d][%d] = %d\n",i,j,f[i][j]);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= cnt; ++i){
        ans +=f[m][i];
        ans %= p;
    }
    cout<<ans<<endl;
    return;
}
}
int main(){
    wzl::main();
    return 0;
}

样例都没过orz