题目描述

奶牛们的牧草快要吃完了！FJ 听了贝茜的抱怨后，买了一块 $M \times N$ 的牧场，牧场可以被分成 $M \times N$ 个格子，有的格子很肥沃，适合放牧。而有的很贫瘠，不适合放牧。

奶牛们的要求很苛刻，每只奶牛必须独占一个格子，并且任意两个奶牛的格子不能相邻（不能有公共的边）。

FJ 要选出一些格子来放牧，他想知道，有多少种方案？

输入

第一行两个数 $M$ ， $N$ 。

接下来 $M$ 行，每行 $N$ 个数，每个数均为 $0$ 或 $1$ ， $0$ 表示不适合放牧， $1$ 表示适合放牧。

对于 $100\%$ 的数据， $N \le 12$ ， $M \le 12$ 。

请注意：FJ 可以直接荒废新买的牧场，即不在任意一个格子放牧，这也算一种方案。

输出

一个数，表示方案数，答案 $\mod 100000000$ 输出。

样例

2 3
1 1 1
0 1 0

9