种植玉米

农夫有一个被划分成M行N列的农田。

每个格子的数字如果是1则表示该格子的土地是肥沃的，可以种植玉米；

如果该格子的数字是0则表示该格子不能种植玉米。

但是还有一个条件：不能出现相邻的两个格子都种植玉米的情况。

问有多少种不同的种植方式。

输入格式

第一行，两个整数，M和N。 1 ≤ M ≤ 15 且 1 ≤ N ≤ 15。 接下来是M行N列的农田，第i行第j列的数字要么是1要么是0。

输出格式

一个整数。答案模100000000。

输入/输出例子1

输入：

2 3

1 1 1

0 1 0

输出：

9