时间限制：1秒　　内存限制：256M

---

【题目描述】

　　在 \(M\) 行 \(N\) 列的棋盘格子上放置若个棋子，有些格子无法放置棋子，且要求任意两个棋子所在的格子不能有公共边。如果不考虑棋子的总块数，那么，一共有多少种放置方案？当然，一个棋子都不放也是一种方案。

【输入格式】

　　第一行：两个整数 \(M\) 和 \(N\)，用空格隔开。
　　第 \(2\) 到第 \(M+1\) 行：每行包含 \(N\) 个用空格隔开的整数，描述了每个格子的状态。第 \(i+1\) 行描述了第 \(i\) 行的格子，所有整数均为 \(0\) 或 \(1\) ，是 \(1\) 的话，表示该格子可以放棋子，\(0\) 则表示无法放棋子。

【输出格式】

　　一个整数，即方案数除以 \(10^8\) 的余数。

【输入输出样例】

　Input

2 3
1 1 1
0 1 0

　Output

9

【样例说明】

　　按下图把各格子编号：

　　只开放一个棋子的话，有4种方案：选1、2、3、4中的任一个格子。若放两个棋子的话，有3种方案：13、14和34。若放三个棋子，只有一种方案：134。再加一个棋子也不放的那一种，总方案数为4+3+1+1=9种。

【数据限制】

　　对于 \(100\%\) 的数据，对于全部数据，\(1≤M,N≤12\)。

【来源】

　　Mr.he