Description

Original Source: USACO 2006 Nov. Gold

Farmer John has recently purchased a new rectangular pasture, which is divided into $M$ rows and $N$ columns $(1≤M≤12; 1≤N≤12)$. Each cell is a square plot of land. FJ plans to plant delicious grass in some of these plots for his cows to enjoy. Unfortunately, some of the land is quite barren and cannot be used for grazing. Additionally, cows prefer to have exclusive access to a grassy area, so FJ will not select two adjacent plots—meaning no two grassy plots share a common edge. Of course, FJ has not yet decided which plots to plant with grass.

As a curious farmer, FJ wants to know how many different planting schemes are available to him, without considering the total number of grassy plots. Leaving the entire pasture unused (i.e., planting no grass at all) also counts as one valid scheme. Please help FJ calculate this total number of schemes.

Input Format

Line $1$: Two positive integers $M$ and $N$, separated by a space;
Lines $2$ to $M+1$: Each line contains $N$ space-separated integers describing the state of each plot. The $(i+1)$-th line describes the plots in the $i$-th row. All integers are either $0$ or $1$, where $1$ indicates the plot is fertile enough, and $0$ means the plot is unsuitable for planting grass.

Output Format

Line $1$: Output an integer, which is the total number of pasture allocation schemes modulo $10^8$.

Sample 1

Label the plots as shown below:

1 2 3
0 4 0

There are $4$ schemes for planting grass in a single plot: choosing any one of $1,$ $2,$ $3,$ or $4$. For planting grass in two plots, there are $3$ schemes: $13,$ $14$, and $34$. There is only one scheme for planting grass in three plots: $134$. Adding the option of leaving the pasture unused, the total number of schemes is $4+3+1+1=9$.

2 3
1 1 1
0 1 0

9

Constraints and Hints

$1\le N,M\le 12$.