solution

状压dp。

用数字来表示一行方案，对于一个状态x，如果x的第i位（二进制下）为1，表示这一行的第i个位置安排士兵。否则表示不安排士兵。

先把每一行可能的状态都搜出来，也就是在满足相邻两个二进制位不都为1的条件下，搜出所有的方案。可以发现一行的方案数最多不超过400。

然后将两个可以转移的状态之间两两连边。x可以转移到y表示的意思是x这个状态可以和y这个状态相邻。判断两个状态之间能不能转移显然就是看x和y是不是有某个二进制位同时为1，即只有时，x可以转移到y。

用表示前i行，第行的状态是y的方案数，注意到，第i行的状态可以是y的前提是y这个状态与所给地形之间不存在某个二进制位置i满足且(b表示第i行的地形状态)。。

考虑转移就从所有的转移过来就行了。转移的条件是j这个状态与k这个状态之间有边。

code

/*
* @Author: wxyww
* @Date:   2020-06-02 19:42:43
* @Last Modified time: 2020-06-02 19:54:25
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 1010,mod = 100000000;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int a[N],ma[N][N],f[20][N],n,m,b[20];

void solve() {    
    int cnt = 0;
    for(int i = 0;i < (1 << m);++i) {
        int flag = 0;
        for(int j = 1;j < m;++j) {
            if((i >> j & 1) && (i >> (j - 1) & 1)) {flag = 1;break;}
        }
        if(!flag) a[++cnt] = i;
    }

    memset(b,0,sizeof(b));
    for(int i = 1;i <= n;++i) {
        for(int j = 0;j < m;++j) {
            int x = read() ^ 1;
            b[i] |= x << j;
        }
    }

    memset(ma,0,sizeof(ma));
    for(int i = 1;i <= cnt;++i) {
        for(int j = i;j <= cnt;++j) {
            if(!(a[i] & a[j])) ma[i][j] = ma[j][i] = 1;
        }
    }
    memset(f,0,sizeof(f));
    f[0][1] = 1;
    // cout<<ma[1][2]<<endl;
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= cnt;++j) {
            if(a[j] & b[i]) continue;
            // if(i == 1 && j == 1) puts("!!!");
            for(int k = 1;k <= cnt;++k) {
                if(ma[k][j]) {
                    // if(k == 1 && i == 1) puts("!!!");
                    f[i][j] += f[i - 1][k],f[i][j] %= mod;
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 1;i <= cnt;++i) 
        ans += f[n][i],ans %= mod;
    cout<<ans<<endl;
}

int main() {
    while(~scanf("%d%d",&n,&m))
    solve();
    return 0;
}