题目描述

农夫有一块 M×N 的长方形牧场，被划分成 M 行 N 列的正方形小格。有的格子土地肥沃，可以种草；有的格子土地贫瘠，不能种草。 奶牛们不喜欢挨着吃草，所以任意两块种了草的格子不能有公共边。

问一共有多少种种草方案。一块草都不种也算一种方案。答案对 100000000 取模。

输入格式

第一行两个整数 M, N。 接下来 M 行，每行 N 个整数（0 或 1），1 表示这块地可以种草，0 表示不能。

输出格式

一个整数，表示方案数对 100000000 取模的结果。

样例

输入

2 3
1 1 1
0 1 0

输出

9

数据范围

1 ≤ M, N ≤ 12。