题目背景

暑假中除了刷题、泡妹子之外，还有一件很严肃的事情——做作业。zxbsmk有个奇怪的习惯，他做作业之前都要先将作业放好，那样才能开心地做作业。

题目描述

zxbsmk有一张长方形的桌子，这张桌子被划分成M (1<=M<=12) 行N (1<=N<=12) 列，每一格都是正方形。
现在他打算在桌子上放作业，以便他去做。遗憾的是，有些位置已经放了东西(手办、杯面……)，不能用来放作业。并且，zxbsmk不会将作业放在相邻的格子里(避免自己分心)，也就是说没有哪两个 放了作业 的格子是有公共边的。
作为一枚蛋疼的死宅，zxbsmk想知道，假如不考虑放多少份作业，一共有多少种放置的方案供他选择。当然，不放任何作业也算一种方案。
请你帮他算一下总方案数。

输入格式：

第1行：两个正整数M和N。
第2到M+1行：每行包括N个整数，描述了每个格子的状态。输入的第i+1行描述第i行的格子。所有的整数均为0或1，是1的话就表示这个格子可以放作业，是0就表示这个格子已经放了东西，不能放作业了。

输出格式：

输出一个整数，即放置作业的总方案数 模100000000 后的结果。

输入样例#1：

2 3
1 1 1
0 1 0

输出样例#1：

9