题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例

2 3
1 1 1
0 1 0

输出样例

9

提示

输出说明:

按下图把各块土地编号：

${1~~ 2~~ 3}$

${~~~~4}$

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

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