L‐Shaped Tiling

The problem is as follows: We are given a grid of size $r\times c$ representing the living room. Some cells may contain pillars (denoted by #) and cannot be tiled, while other cells are empty (denoted by .). You have an unlimited supply of L–shaped tiles. An L–shaped tile is defined by two perpendicular arms meeting at a corner. Formally, an L–shaped tile is determined by two positive integers $a\ge1$ and $b\ge1$ so that the tile covers $a+b-1$ cells. For example, one way to place an L–shaped tile is as follows:

• Orientation 1 (down–right): if the top–left cell of the tile is at $(r_0,c_0)$, then the tile covers the cells \( (r_0,c_0), (r_0,c_0+1),\dots,(r_0,c_0+a-1) \) (the horizontal arm) and \( (r_0,c_0), (r_0+1,c_0),\dots,(r_0+b-1,c_0) \) (the vertical arm).

There are in fact four possible orientations. However, note that when the arms are of minimal length (i.e. $a=1$ or $b=1$), some placements in different orientations result in the same set of cells. In our counting, such coverings are considered identical. To avoid double counting, we use the following convention based on the minimal (top–left) cell of the tile (in row–major order): when placing a new tile we choose the first uncovered cell and then only consider placements whose minimum cell is that cell. Moreover, we only enumerate:

• Orientation 1: allowed for any $a\ge1,b\ge1$.
• Orientation 2 (down–left): only when $a>1$ (so that the horizontal arm extends to the right more than one cell) to avoid duplicating 1–cell horizontal tiles.
• Orientation 3 (up–right): only when $b>1$.
• Orientation 4 (up–left): only when $a>1$ and $b>1$.

Your task is to count, in how many different ways one can cover all the empty cells of the grid with such L–shaped tiles — each tile may have a different size and orientation, but tiles cannot overlap and cannot cover any cell with a pillar. All empty cells must be covered.

inputFormat

The first line contains two integers $r$ and $c$ ($1 \le r,c \le 8$), representing the number of rows and columns, respectively. Then follow $r$ lines, each containing a string of length $c$. Each character is either . (an empty cell) or # (a pillar that cannot be tiled).

outputFormat

Output a single integer — the number of different ways to tile the given grid using L–shaped tiles as described.

sample

1 1
.

1