Description

A company abbreviated as LLL is designing a logo. Their initial plan is to place $3$ L-shaped patterns and some extra decorative shapes on a square grid, for example: (the gray area denotes decorative shapes).

The $3$ L-shaped patterns and the decorative shapes are all placed on the grid, and together they must cover the entire grid. The horizontal and vertical strokes of each L may have any positive length, but each length must be greater than $0$ (i.e., an L cannot degenerate into a straight line segment). In addition, to keep the L patterns clear and recognizable, the $3$ L-shaped patterns must not overlap or cross each other. Of course, an L-shaped pattern also cannot pass through or overlap any decorative shape.

Now that the designer has fixed the positions of all decorative shapes, please compute how many different logos can be designed by placing the L-shaped patterns.

Input Format

The first line contains two space-separated positive integers $n$ and $m$, the numbers of rows and columns of the grid.

The next $n$ lines each contain $m$ characters. In the $(i + 1)$-th line, the $j$-th character denotes the cell at row $i$, column $j$. Each character is either . or #. # means the cell is a decorative shape, and . means it is an empty cell where an L-shaped pattern may be placed.

Output Format

Output a single integer, the total number of possible logos.

4 4
....
#...
....
..#.

4

Hint

Constraints

For $100\%$ of the testdata, $2\le n,m\leq 30$.

Translated by ChatGPT 5