Corn Fields


Farmer Christine has purchased a lush new rectangular pasture composed
of M by N (1 <= M <= 12; 1 <= N <= 12) square parcels. She wants to
grow some yummy corn for the cows on a number of squares. Regrettably,
some of the squares are infertile and can't be planted. Canny FC
knows that the cows dislike eating close to each other, so when
choosing which squares to plant, she avoids choosing squares that
are adjacent; no two chosen squares share an edge. She has not yet
made the final choice as to which squares to plant.

Being very open-minded, Farmer Christine wants to consider all
possible options for how to choose the squares for planting. She is
so open-minded that she considers planting no squares a valid
option, too.  Please help Farmer Christine determine the number
of ways she can choose the squares to plant.

PROBLEM NAME: cornfields

INPUT FORMAT:

* Line 1: Two space-separated integers: M and N

* Lines 2..M+1: Line i+1 describes row i of the pasture with N
        space-separated integers indicating whether a square is
        fertile (1 for fertile, 0  for infertile)

SAMPLE INPUT:

2 3
1 1 1
0 1 0

OUTPUT FORMAT:

* Line 1: One integer: the number of ways that FC can choose the
        squares modulo 100,000,000.

SAMPLE OUTPUT:

9

OUTPUT DETAILS:

Number the squares as follows:

1 2 3
  4

There are four ways to plant only on one squares (1, 2, 3, or 4),
three ways to plant on two squares (13, 14, or 34), 1 way to plant
on three squares (134), and one way to plant on no squares. 4+3+1+1=9.