327. 玉米田

// 327. 玉米田.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;


/*
https://www.acwing.com/problem/content/329/

农夫约翰的土地由 M×N 个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式
第 1 行包含两个整数 M 和 N。

第 2..M+1 行：每行包含 N 个整数 0 或 1，用来描述整个土地的状况，1 表示该块土地肥沃，0 表示该块土地不育。

输出格式
输出总种植方法对 108 取模后的值。

数据范围
1≤M,N≤12
输入样例：
2 3
1 1 1
0 1 0
输出样例：
9
*/
const int N = 12;
long long dp[N+5][1<<N];
int f[N+5];
int n, m;
const int MOD = 1e8;


bool check(int a, int b) {
	if ( (a & b) != 0) return false;
	return true;
}

bool rule(int x) {
	int state = 0;
	while (x != 0) {
		if (x & 1 && state == 1) return false;
		state = x & 1;
		x >>= 1;
	}

	return true;
}



int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int t = 0;
		for (int j = 0; j < m; j++) {
			int a; cin >> a;
			if (a == 0) t += 1 << j;
		}
		f[i] = t;
	}

	dp[0][0] = 1;

	for (int i = 1; i <= n+1; i++) {
		for (int prev = 0; prev < 1 << m; prev++) {
			if (rule(prev) == false) continue;
			for (int curr = 0; curr < 1 << m; curr++) {
				if (rule(curr) == false) continue;
				if (check(prev, curr) && check(curr, f[i])) {
					dp[i][curr] += dp[i - 1][prev];
					dp[i][curr] %= MOD;
				}
			}
		}
	}
	long long ans = 0;
	for (int curr = 0; curr < 1 << m; curr++) {
		ans += dp[n][curr];
		ans %= MOD;
	}
	cout << ans << endl;


	return 0;
}