#2592. 玉米田

玉米田

Description

约翰购买了由m×n1mn12m×n(1≤m,n≤12)的方格组成的矩形牧场,想在一些方格上种玉米。遗憾的是,有些方格土壤贫瘠,无法种植。约翰在选择种植哪些方格时,会避免选择相邻的方格,没有两个选定的方格共享一条边。约翰考虑了所有可能的选择,他认为没有选择方格也是一种有效的选择!帮助他选择种植方格的方案数。

Format

Input

11行包含以两个空格分隔的整数mmnn。后面有mm行,每行都包含nn个整数,表示一个方格是否肥沃(11表示肥沃,00表示贫瘠)。

Output

单行输出选择种植方格的方案数模100000000100000000

Samples

2 3
1 1 1
0 1 0
9

来源

POJ3254