#3749. 玉米田

玉米田

玉米田

题目描述

农夫约翰的土地由 M×NM \times N 个小方格组成,现在他要在土地里种植玉米。

非常遗憾,部分土地太贫瘠,无法种植。而且,相邻的土地不能同时种植玉米,也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小和每个方格的状况,请你求出一共有多少种种植方法。土地上什么都不种也算一种方法。

输入格式

第 1 行包含两个整数 MM 和 NN。

第 22 到第 M+1M+1 行,每行包含 NN 个整数 00 或 11,用来描述整个土地的状况:11 表示该块土地肥沃可以种植,00 表示该块土地贫瘠不能种植。

输出格式

输出一行,包含一个整数,表示总种植方法数对 100000000100000000 取模后的值。

样例输入

2 3
1 1 1
0 1 0

样例输出

9

样例解释

把肥沃的四个方格分别记为 A,B,CA,B,C(第一行)和 DD(第二行中间)。所有合法方案包括:

  • 什么都不种:1 种;
  • 只种一个方格:4 种;
  • 种两个不相邻的方格:(A,C)(A,C)、(A,D)(A,D)、(C,D)(C,D),共 3 种;
  • 种三个方格:(A,C,D)(A,C,D),共 1 种。

合计 1+4+3+1=91+4+3+1=9 种。

数据范围

对于全部测试数据,保证 1≤M,N≤121 \le M, N \le 12,方格只由整数 00 或 11 组成。