Description

约翰购买了由$m×n（1≤m，n≤12）$的方格组成的矩形牧场，想在一些方格上种玉米。遗憾的是，有些方格土壤贫瘠，无法种植。约翰在选择种植哪些方格时，会避免选择相邻的方格，没有两个选定的方格共享一条边。约翰考虑了所有可能的选择，他认为没有选择方格也是一种有效的选择！帮助他选择种植方格的方案数。

Format

Input

第$1$行包含以两个空格分隔的整数$m$和$n$。后面有$m$行，每行都包含$n$个整数，表示一个方格是否肥沃（$1$表示肥沃，$0$表示贫瘠）。

Output

单行输出选择种植方格的方案数模$100000000$。

Samples

2 3
1 1 1
0 1 0

9

来源

POJ3254