Counting Valid Loop Configurations in a Grid

You are given an n × m grid. Each cell of the grid is either allowed or blocked. In an allowed cell, you must place a line tile; in a blocked cell, you cannot place any tile. There are exactly two types of line tiles:

• / tile: connects the top‐right and bottom‐left vertices of the cell.
• \ tile: connects the top‐left and bottom‐right vertices of the cell.

The grid vertices are the intersection points of the grid lines; there are (n+1) × (m+1) vertices in total. A configuration of tiles is valid if, when each allowed cell is assigned one of the two tiles, the connectivity induced on the vertices is such that every vertex has an even degree (i.e. 0, 2, or 4 incident line‐segments). In other words, the drawn lines form one or more closed loops without any dangling endpoints.

Your task is to count the number of valid tilings.

Note: All formulas are given in LaTeX format. For example, the grid size is given as \(n \times m\) and the total number of vertices is \((n+1) \times (m+1)\).

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of rows and columns of the grid. Each of the following \(n\) lines contains \(m\) space‐separated integers. Each integer is either 0 or 1, where 0 means the cell is blocked (no tile can be placed) and 1 means the cell is allowed (a tile must be placed).

Constraints: Since a brute force solution is used, it is guaranteed that the number of allowed cells is small (for example, \(n, m \le 5\)).

outputFormat

Output a single integer — the total number of valid tilings that form only closed loops.

sample

1 1
1

0