题目描述

坤坤是一个热爱踢足球的少年，他新获得了一块长方形的足球场，这块足球场被划分成 $M$ 行 $N$ 列（$1 \leq M \leq 12$，$1 \leq N \leq 12$），每一格都是一块正方形的草皮。坤坤希望在某些格子上种植真草皮，这样他就可以在上面踢足球了。

然而，有些草皮质量较差，不适合种植真草。此外，为了节约经费，坤坤不会选择两块相邻的草皮种植真草，也就是说，没有哪两块真草皮有公共边。

坤坤想知道，如果不考虑种植真草皮的总块数，那么一共有多少种种植方案可供他选择？（当然，完全不种植任何真草皮也是一种方案）

输入格式

• 第一行：两个整数 $M$ 和 $N$，用空格隔开。
• 第 $2$ 到第 $M+1$ 行：每行包含 $N$ 个用空格隔开的整数，描述了每块土地的状态。第 $i+1$ 行描述了第 $i$ 行的土地，所有整数均为 $0$ 或 $1$，是 $1$ 的话，表示这块土地足够肥沃，$0$ 则表示这块土地不适合种草。

输出格式

一个整数，即牧场分配总方案数除以 $100,000,000$ 的余数。

数据范围

• $1 \leq M \leq 12$
• $1 \leq N \leq 12$

输入样例

2 3
1 1 1
0 1 0

输出样例

9