Problem 23719 --奶牛的食物

23719: 奶牛的食物

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 92  Solved: 59
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

Description

      奶牛们的牧草快要吃完了!FJ 听了贝茜的抱怨后,买了一块 M*N 的牧场,牧场可以被分成 M*N 个格子,有的格子很肥沃,适合放牧。而有的很贫瘠,不适合放牧。奶牛们的要求很苛刻,每只奶牛必须独占一个格子,并且任意两个奶牛的格子不能相邻。FJ 要选出一些格子来放牧,他想知道,有多少种方案?

Input

第一行两个数 M,N
接下来 M 行,每行 N 个数,每个数均为 0 或 1,0 表示不适合放牧,

1 表示适合放牧


【Hint】
FJ 可以直接荒废新买的牧场,即不在任意一个格子放牧,这也算一
种方案
对于 100%的数据,N<=12,M<=12

Output

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

Sample Input

2 3
1 1 1
0 1 0

Sample Output

9

HINT

Source

[Submit][Status]