题目描述

PKU 3254

事实证明,理想和现实总是存在差距,修罗王到了战场才发现，猛兽军团只能放置在一个 $\red{M\times N}$的矩阵,而且部分方格由于地形限制无法放置猛兽,请问猛兽与猛兽若不能相邻,有多少种放置方案?

注:经过修罗王的三观教育,猛兽之间的关系略显缓和,但仍不能彼此相邻

输入格式

第一行:两个整数$\red{M(0≤}$$\red{M≤}$$\red{12)}$和$\red{N(1≤}$$\red{N≤}$$\red{12)}$。

接下去$\red{M}$行:每行包括$\red{N}$个用空格隔开的整数,$\red{0}$代表不可放置,$\red{1}$代表可以放置。

输出格式

放置方案个数,个数可能较大,取$\red{100 000 000}$的余数。

样例

输入样例

2 3
1 1 1
0 1 0

输出样例

9