#668. 牧场的安排

牧场的安排

题目描述

农场主FJ新买了一块长方形的新牧场,这块牧场被划分成 MMNN 列,每一格都是一块正方形的土地。FJ打算在牧场上的某几格里种上美味的草,供他的奶牛们享用。

遗憾的是,有些土地相当贫瘠,不能用来种草。并且,奶牛们喜欢独占一块草地的感觉,于是FJ不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。

FJ想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择?(当然,把新牧场完全荒废也是一种方案)

输入格式

第一行:两个整数 MMNN,用空格隔开。

22 到第 M+1M+1 行:每行包含 NN 个用空格隔开的整数,描述了每块土地的状态。第 i+1i+1 行描述了第 ii 行的土地,所有整数均为 0011 ,是 11 的话,表示这块土地足够肥沃,00 则表示这块土地不适合种草。

输出格式

一个整数,即牧场分配总方案数除以 10810^8 的余数。

2 3
1 1 1
0 1 0
9

数据范围

1N,M121 \le N,M \le 12