思路是 先预处理出所有同行不相邻的合法状态，

dp 的时候额外判断一下对该行调用的状态是否合法（状态中种了草的地方是否都可以种草），

然后如果当前行与上一行的状态不矛盾，就累加贡献

#include <bits/stdc++.h>
#define re register int 

using namespace std;
typedef long long LL;
const int maxs = 8200, mod = 1e8;

int n, m, g[20][20], ok[maxs], num;
LL f[20][maxs];

inline void init()
{
	for (re j = 1; j <= m; j ++) g[0][j] = 1;
	for (re s = 0; s < (1 << m); s ++)
	{
		if ((((s << 1) | (s >> 1)) & s) == 0) ok[++ num] = s;
	}
}

inline bool check(int s, int i)
{
	int j = m;
	bool flag = false;
	
	while (s)
	{
		if ((s & 1) && !g[i][j])
		{
			flag = true;
			break;
		}
		s >>= 1;
		j --;
	}
	return flag; 
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (re i = 1; i <= n; i ++)
		for (re j = 1; j <= m; j ++) cin >> g[i][j];
	init();
	
	f[0][0] = 1;
	for (re i = 1; i <= n; i ++)
		for (re u = 1; u <= num; u ++)
		{
			int su = ok[u];
			if (check(su, i)) continue;
			for (re v = 1; v <= num; v ++)
			{
				int sv = ok[v];
				if (check(sv, i - 1)) continue;
				if ((su & sv) == 0) f[i][sv] += f[i - 1][su];
			}
		}
	LL res = 0;
	for (re s = 1; s <= num; s ++) res = (res + f[n][ok[s]]) % mod;
	cout << res << '\n';
	
//	cout << num << '\n';
	
	return 0;
}