题目描述

农夫约翰的土地由$\red {M\times N}$个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式

第$\red {1}$行包含两个整数$\red {M}$和$\red {N}$。

第$\red {2..M+1}$行：每行包含$\red {N}$个整数$\red {0}$或$\red {1}$，用来描述整个土地的状况，$\red {1}$表示该块土地肥沃，$\red {0}$表示该块土地不育。

输出格式

输出总种植方法对$\red {100000000}$取模后的值。

样例

输入样例

2 3
1 1 1
0 1 0

输出样例

9

提示

$\red {1≤M,N≤12}$