德玛西亚万岁

题意：n*m的矩阵 1能站人，0不能站人，相邻的地方不能站人，问总方案数？

题解：知识点状态DP.
通过题意我们可以知道：
1，当位置(i,j)为0时，不能站人。
2，如果(i,j)站人，那么[i-1,j],[i+1,j],[i,j+1],[i,j-1]这四个地方不能站；
因为数据量不是很大所以我们可以想到用二进制来表示当前该位置上是否站人。
针对1，我们可以样做，因为那这个位置不能站人，所以他这个为对应的二进制位为0，这样之后判断就可以知道，这个位置可不可以站人了。
针对2，我们先看左右的，由于我们把能不能站人转化成了二进制，那么我们也可以用二进制来表示那些位置上站没站人，然后利用错位来判断是否有相邻的，例如

1010101//原本的二进制
 101010//错位之后的二进制
0000000//比较之后

比较之后如果是零就说明他没有相邻的。而如果有相邻的就是这种情况

11011000//原
01101100//错
01001000//结果

我们可以知道前一对11和后一对11他们是相邻的所以返回值不是0；

然后我们看上下：其实就是在枚举一遍上一层的二进制站位，原理跟左右一样，就是这一层是上一层继承过来的，所以若果没有相邻的也要加上上层的那个状态，
最后不要忘了，一个都不放也是一种方案；

代码：

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=100000000;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆         小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下       大根堆      大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[20][1<<16];
string str,s;

#define read read()
int main(){    
     while(~scanf("%lld%lld",&n,&m)){
        p=(1<<m);//总的二进制方案数
        //每次初始化
        for(int i=1;i<=n;i++) dis[i]=0;
        for(int i=0;i<=n;i++)
            for(int j=0;j<p;j++) 
                dp[i][j]=0;

        dp[0][0]=1;//什么都不放也算一种方案数
        for(int i=1;i<=n;i++)
            for(int j=0;j<m;j++){
                cin>>l;
                dis[i]=dis[i]|(l<<j);//判断这一个位置有没有 用二进制表示
            }


        for(int i=1;i<=n;i++){            
            for(int j=0;j<p;j++){//用二进制表示当前的状态
                //没有这种状态
                if((j&dis[i])!=j)continue;

                //左右相邻了
                if(j&(j>>1))continue;

                for(int k=0;k<p;k++){
                    if(k&j) continue;//上下相邻了 
                    else dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;//可以从上层转移过来
                }
            }
        }
        ans=0;
        for(int i=0;i<p;i++){
            ans=(ans+dp[n][i])%mod;
        }
        cout<<ans<<endl;



    }
    return 0;
}