题目描述

德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。

有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。结果比尔吉沃特领土太小，只有长为 $n$ 宽为 $m$ 共计 $n*m$ 块土地，其中有些土地标记为 $0$ 表示为高山峻岭或者深海湖泊，英雄们无法在其中站立，只有标记为 $1$ 的土地才能容纳一个英雄。德玛西亚的英雄们战斗时有一个特点，他们不希望队友站在自己旁边显得很暧昧。请问最多能有多少种安排德玛西亚英雄的方法？

输入格式

输入有多组测试样例。

每组数据有 $n+1$ 行。

第一行包含 $2$ 个整数 $n$ 和 $m$，之间用空格隔开。

接下来的 $n$ 行，每行 $m$ 个数，表示 $n*m$ 的比尔吉沃特领土。

输出格式

输出一个整数 $n$ 代表安排应用的方法。（答案取模 $100000000$）

样例输入输出

样例输入

3 3
1 1 1
0 1 1
1 0 0

样例输出

24

数据范围

对于 $100%$ 的数据，保证 $n \le 12,m \le 12$