一块 $M \times N$ 的田， $1$ 表示这个地方可以种植， $0$ 代表这个地方不能种植。

植物种植还必须满足两株植物不能相邻（横竖都不行）。

问共有几种种植方法，而且当什么都不种时认为是一种方法。

输入格式

第一行为 $M,N$

接下来 $M$ 行 $N$ 个 $0$ , $1$ 代表第 $m$ 行第 $i$ 列的方块能否种植植物

输出格式

一个整数对100,000,000取模

样例

样例输入

2 3
1 1 1
0 1 0

样例输出

9

来源

数据范围与提示

• 时间限制： $1000\mathrm{ms}$
• 空间限制： $131022\mathrm{KB}$
• 对于 $30$ %的数据, $1 \leq n,m \leq 5$
• 对于 $100$ %的数据, $1 \leq n,m \leq 12$