该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

约翰新买了一块长方形的牧场．这块牧场被划分成M 列N 行(1 <= M <= 12; 1 <= N <= 12)，每 一格都是一块正方形的土地．约翰打算在牧场上的某几格土地里种上美昧的草，供他的奶牛们享 用．遗憾的是，有些土地相当的贫瘠，不能用来放牧．并且，奶牛们喜欢独占一块草地的感觉，于是约翰不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边．当然，约翰还没有决 定在哪些土地上种草．

作为一个好奇的农场主，约翰想知道，如果不考虑草地的总块数，那么，一共有多少种种植 方案可供他选择．当然，把新的牧场荒废，不在任何土地上种草，也算一种方案．请你帮约翰算 一下这个总方案数．

输入说明

第1行：两个正整数M 和N ．

第2到M + 1行：每行包含N 个整数，描述了每块土地的状态．输入的第i + 1行描述了第i行的 土地．所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块地上不适合种草．

输出说明

输出一个整数，即牧场分配总方案数除以100000000的余数．

输入样例

2 3
1 1 1
0 1 0

输出样例

9

样例说明

把各块土地编号：

1 2 3

0 4 0

只开辟一块草地的话，有4种方案．选1、2、3、4中的任一块；开辟两块草地的话，有3种方案．1、3，1、4以及3、4；选三块草地只有一种方案．1、3、4；再加把牧场荒废的那一种，总方案数为4 + 3 + 1 + 1 = 9种．

来源信息

Richard Ho, 2006