Grass Planting

Farmer John has acquired a rectangular pasture divided into M rows and N columns, where 1 ≤ M ≤ 12 and 1 ≤ N ≤ 12. Each cell represents a square parcel of land. Some parcels are infertile and cannot be used for planting. John wants to plant grass on a subset of the fertile parcels. However, the cows prefer exclusive access to a grassland so John will never plant grass on two adjacent parcels (i.e. two planted parcels must not share an edge).

Compute the number of possible planting schemes, where it is allowed to not plant on any square at all.

In mathematical terms, let each cell be denoted by a coordinate. John can choose any set of fertile cells, subject to the constraint that if a cell (i, j) is chosen, then none of its 4 edge-adjacent neighbors ((i-1, j), (i+1, j), (i, j-1), (i, j+1)) is chosen. The answer is the total number of valid selections.

The constraint for two cells not to be adjacent can be expressed in LaTeX as:

[ \text{If } (i,j) \text{ and } (k,l) \text{ are both chosen, then } |i-k| + |j-l| \neq 1. ]

inputFormat

The first line contains two integers M and N, representing the number of rows and columns of the pasture respectively.

Each of the following M lines contains N integers. Each integer is either 1 or 0, where 1 indicates a fertile parcel and 0 indicates an infertile parcel.

outputFormat

Output a single integer: the number of valid planting schemes where no two planted parcels are adjacent.

sample

2 2
1 1
1 1

7