Corn Fields

Farmer John has purchased a lush new rectangular pasture made up of $M \times N$ ($1 \le M \le 12$, $1 \le N \le 12$) square parcels. He wants to grow some tasty corn for the cows on a number of the squares. Unfortunately, some of the squares are infertile and cannot be planted.

The cows dislike eating close to one another, so when Farmer John chooses which squares to plant, he never chooses two squares that are adjacent (two squares that share an edge).

Being very open-minded, Farmer John wants to consider every possible way of choosing the squares to plant — he even counts planting no squares at all as a valid option! Please help him determine the number of ways he can choose the squares to plant.

• Line 1: Two space-separated integers, $M$ and $N$
• Lines $2$ to $M+1$: Line $i+1$ describes row $i$ of the pasture with $N$ space-separated integers indicating whether each square is fertile ($1$) or infertile ($0$)

• Line 1: A single integer — the number of ways Farmer John can choose the squares to plant, modulo 100,000,000.

Consider a $2 \times 3$ pasture in which the entire top row is fertile and only the center square of the bottom row is fertile. Label the fertile squares 1, 2, 3 (top row, left to right) and 4 (bottom-center). There are 4 ways to plant a single square (1, 2, 3, or 4), 3 ways to plant two squares ((1,3), (1,4), or (3,4)), 1 way to plant three squares ((1,3,4)), and 1 way to plant no squares, for a total of 4+3+1+1 = 9.