题目描述
展会场地划分为 $M$ 行 $N$ 列的格子，部分格子可用（记 $1$）、部分不可用（记 $0$）。 现在要在可用格子里摆放展位，要求任意两个展位不相邻（无公共边）。 求摆放方案总数（含全不摆），对 $10^8$ 取模。
输入格式
第一行两个正整数 $M, N$（$1 \le M, N \le 12$）。 接下来 $M$ 行每行 $N$ 个整数（$0$ 或 $1$）：第 i 行第 j 列的格子可用性。
输出格式
一行一个整数：总方案数对 $10^8$ 取模。
数据范围
None
展会场地划分为 $M$ 行 $N$ 列的格子，部分格子可用（记 $1$）、部分不可用（记 $0$）。 现在要在可用格子里摆放展位，要求任意两个展位不相邻（无公共边）。 求摆放方案总数（含全不摆），对 $10^8$ 取模。
第一行两个正整数 $M, N$（$1 \le M, N \le 12$）。 接下来 $M$ 行每行 $N$ 个整数（$0$ 或 $1$）：第 i 行第 j 列的格子可用性。
一行一个整数：总方案数对 $10^8$ 取模。
None
2 3 1 1 1 0 1 0
9
1 1 1
2