2156 - 奶牛的食物

题目描述

奶牛们的牧草快要吃完了!FJ 听了贝茜的抱怨后,买了一块 M*N 的牧场,牧场可以被分成 M*N 个格子,有的格子很肥沃,适合放牧。而有的很贫瘠,不适合放牧。

奶牛们的要求很苛刻,每只奶牛必须独占一个格子,并且任意两个奶牛的格子不能相邻(不能有公共的边)。

FJ 要选出一些格子来放牧,他想知道,有多少种方案?

输入

第一行两个数 MN

接下来 M 行,每行 N 个数,每个数均为 010 表示不适合放牧,1 表示适合放牧。

对于 100\% 的数据,N <= 12 , M <= 12

请注意:FJ 可以直接荒废新买的牧场,即不在任意一个格子放牧,这也算一种方案。

输出

一个数,表示方案数,答案 mod 100000000 输出

样例

输入

2 3
1 1 1
0 1 0

输出

9
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题