Migrated from Lutece 882 冬马党

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

终于到了冬马党与雪菜党决战的时候了，为了方便，他们的决战之地可看成一个$n \times m$矩阵。

决战前夜，冬马党安插在雪菜党中的内线告诉白学家Kuros，雪菜党已经在他们的决战之地埋下了地雷。

白学家Kuros根据多年来扫雷的经验，推测出雪菜党一定不会在相邻的格子里都放地雷。(两个格子相邻指它们共享一条边)并且，根据先遣部队的探查，某些格子的土地非常坚硬，是不可能埋地雷的。

为了冬马党最终的胜利，Kuros想知道，雪菜党总共有多少种方案来放地雷。

Input

输入第一行为两个整数$n，m$，表示决战之地的大小。$(1 \leq n \leq 12 , 1 \leq m \leq 12)$

接下来$n$行，每行$m$个数，$0$表示该土地不能放地雷，$1$表示该土地可以埋地雷。

Output

一行，一个整数，表示总的方案数，答案取$100000000$的余数。

Samples

2 3
1 1 1
0 1 0

9

Resources

2014 UESTC Training for Dynamic Programming