好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：USACO 2006 Nov. Gold

Farmer John 新买了一块长方形的牧场，这块牧场被划分成 $M$ 行 $N$ 列 $(1 \le M \le 12; 1 \le N \le 12)$，每一格都是一块正方形的土地。FJ 打算在牧场上的某几格土地里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当的贫瘠，不能用来放牧。并且，奶牛们喜欢独占一块草地，于是 FJ 不会选择两块相邻的土地，即：没有哪两块草地有公共边（上下左右相邻）。当然，FJ 还没有决定在哪些土地上种草。

作为一个好奇的农场主，FJ 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择。当然，把新的牧场荒废，不在任何土地上种草，也算一种方案。请你帮 FJ 算一下这个总方案数。输出答案对 $10^8$ 取模的结果。

---

输入格式

• 第 $1$ 行：两个正整数 $M$ 和 $N$，用空格隔开；
• 第 $2$ 到 $M+1$ 行：每行包含 $N$ 个用空格隔开的整数，描述了每块土地的状态。输入的第 $i+1$ 行描述了第 $i$ 行的土地。所有整数均为 $0$ 或 $1$，$1$ 表示这块土地足够肥沃，$0$ 则表示这块地上不适合种草。

---

输出格式

输出一个整数，即牧场分配总方案数除以 $10^8$ 的余数。

---

样例

样例输入

2 3
1 1 1
0 1 0

样例输出

9

样例说明

牧场土地（1表示肥沃，0表示贫瘠）：

1 1 1
0 1 0

按位置编号：

(1,1) (1,2) (1,3)
(2,1) (2,2) (2,3)

其中肥沃的土地有：(1,1),(1,2),(1,3),(2,2)。

方案数：

1. 不种任何草：1 种
2. 只种一块草地：选 (1,1) 或 (1,2) 或 (1,3) 或 (2,2)，共 4 种
3. 种两块草地（不能相邻）：
   • (1,1) 和 (1,3)
   • (1,1) 和 (2,2)
   • (1,3) 和 (2,2) 共 3 种
4. 种三块草地：只能选 (1,1),(1,3),(2,2)，共 1 种

总方案数：$1+4+3+1 = 9$。

---

数据范围

对于全部数据，$1 \le N,M \le 12$。

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为 状态压缩 DP 问题，类似“玉米田”问题。

状态设计：

• 用二进制数表示一行的种植情况：$1$ 表示种，$0$ 表示不种；
• 状态必须满足：
  1. 同一行内不能有两个相邻的 $1$（因为不能左右相邻）；
  2. 状态中的 $1$ 只能出现在肥沃的土地上（即对应的格子必须为 $1$，否则不能种）。
• 相邻两行之间，上下不能同时为 $1$（因为不能上下相邻）。

设 $dp[i][s]$ 表示前 $i$ 行，且第 $i$ 行状态为 $s$ 的方案数。

转移方程：

$$dp[i][s] = \sum_{s'} dp[i-1][s']$$

其中 $s'$ 是第 $i-1$ 行的状态，且满足：

1. $s$ 与 $s'$ 没有上下相邻的 $1$（即 $s \& s' = 0$）；
2. $s$ 和 $s'$ 各自内部没有左右相邻的 $1$；
3. $s$ 必须与第 $i$ 行的肥沃情况兼容（即 $s$ 的 $1$ 位对应位置的土地必须为 $1$）。

初始化：$dp[0][0] = 1$（第 $0$ 行，不种任何草地）。

最终答案：

$$\text{ans} = \sum_{s} dp[M][s] \pmod{10^8}$$

优化：

• 预处理所有合法行状态（无相邻 $1$）；
• 预处理状态间的兼容性（上下不冲突）；
• 对于每行，预处理该行允许的状态（状态中的 $1$ 必须对应肥沃土地）。

复杂度：$O(M \times |S|^2)$，其中 $|S|$ 是合法行状态数，对于 $N \le 12$，$|S| \le 2^{12} = 4096$，但实际合法状态少得多（约几百个），可以接受。