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

题目描述

$\red{Farmer John}$新买了一块长方形的牧场，这块牧场被划分成$\red{M}$列$\red{N}$行$\red{(1<=M<=12}$; $\red{1<=N<=12)，}$每一格都是一块正方形的土地。$\red{FJ}$打算在牧场上的某几格土地里种上美味的草，供他的奶牛们享用。

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

当然，$\red{FJ}$还没有决定在哪些土地上种草。 作为一个好奇的农场主，$\red{FJ}$想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择。

当然，把新的牧场荒废，不在任何土地上种草，也算一种方案。请你帮$\red{FJ}$算一下这个总方案数。

输入格式

第$\red{1}$行: 两个正整数$\red{M}$和$\red{N，}$用空格隔开

第$\red{2...M+1}$行: 每行包含$\red{N}$个用空格隔开的整数，描述了每块土地的状态。输入的第$\red{i+1}$行描述了第$\red{i}$行的土地。

所有整数均为$\red{0}$或$\red{1，}$是$\red{1}$的话，表示这块土地足够肥沃，$\red{0}$则表示这块地上不适合种草

输出格式

第$\red{1}$行: 输出一个整数，即牧场分配总方案数除以$\red{100,000,000}$的余数

样例

输入样例

2 3
1 1 1
0 1 0

输出样例

9

提示

输出说明:

按下图把各块土地编号：

$\red{1~~ 2~~ 3}$

$\red{0~~4~~0}$

只开辟一块草地的话，有$\red{4}$种方案：选$\red{1}$、$\red{2}$、$\red{3}$、$\red{4}$中的任一块。

开辟两块草地的话，有$\red{3}$种方案：$\red{13}$、$\red{14}$以及$\red{34}$。选三块草地只有一种方案：$\red{134}$。再加把牧场荒废的那一种，总方案数为$\red{4+3+1+1=9}$种。