LLL Company Logo Design

A company abbreviated as LLL is designing its logo. Their initial plan is to cover a rectangular grid completely with exactly three L‐shaped pieces together with some decorative patterns. The decorative patterns are fixed on the grid and the remaining cells must be exactly filled by the three L–shaped pieces.

An L–shaped piece is defined as follows. It consists of a corner cell and two perpendicular "arms”. Formally, if the corner is at cell \((i,j)\), then for two chosen perpendicular directions (for example, right and down), if the horizontal arm extends by a cells and the vertical arm extends by b cells (with both a and b being positive, i.e. at least 1), the piece covers the cells:

[ { (i, j) } \cup { (i, j+ k) : 1 \le k \le a } \cup { (i+ k, j) : 1 \le k \le b } ]

In other words, its area is \(a+b+1\). Different choices of a and b (and different orientations, i.e. any 90° rotation is allowed) yield different L–shapes. In addition, the three L–shaped pieces must not overlap or cross each other, and they cannot cover any cell occupied by a decorative figure.

The grid is completely filled – every cell is either covered by one of the three L–shaped pieces or is occupied by a decorative pattern. Given the fixed positions of the decorative figures, your task is to calculate how many different logos (i.e. placements of the three L–shaped pieces) can be designed.

Note: All L–shaped pieces use cells from the grid. When placing an L–shaped piece, all cells covered by that piece must lie inside the grid and must be free (i.e. not already occupied by a decorative pattern or by another L–shaped piece).

inputFormat

The first line contains two integers n and m (the number of rows and columns of the grid).

Then follow n lines, each containing a string of length m. Each character is either a . (denoting an empty cell in which an L–piece may be placed) or a # (denoting a cell occupied by a decorative figure).

outputFormat

Output a single integer – the total number of valid ways to place the three L–shaped pieces so that the grid is exactly covered.

sample

2 2
..
..

0