描述
农夫约翰（Farmer John）购买了一块由$M \times N$（$1 \leq M \leq 12$；$1 \leq N \leq 12$）个正方形地块组成的新矩形牧场。他想在一些地块上为奶牛种植美味的玉米。遗憾的是，部分地块贫瘠，无法种植。机智的FJ知道奶牛不喜欢彼此靠近进食，因此在选择种植地块时，他会避免选择相邻的地块；即任何两个被选中的地块不能共享一条边。他尚未最终确定种植哪些地块。

作为一个思想非常开放的人，农夫约翰希望考虑所有可能的种植方案。他甚至认为不种植任何地块也是一种有效的选择！请帮助农夫约翰计算他可以选择种植地块的总方式数。

输入
第1行：两个用空格分隔的整数$M$和$N$
第2..$M+1$行：第$i+1$行描述牧场的第$i$行，包含$N$个用空格分隔的整数，表示地块是否肥沃（1表示肥沃，0表示贫瘠）

输出
第1行：一个整数，表示FJ可以选择种植地块的方式数，结果对$100,000,000$取模。

输入样例 1

2 3  
1 1 1  
0 1 0

输出样例 1

9

提示
将地块编号如下：

1 2 3
4

种植一个地块的方式有4种（1、2、3或4），种植两个地块的方式有3种（13、14或34），种植三个地块的方式有1种（134），不种植地块的方式有1种。总数为$4+3+1+1=9$。

来源
USACO 2006 November Gold