A company with the abbreviation LLL is designing a logo. Their initial plan is to place three L-shaped patterns and some additional decorative shapes on a grid. For example:
(The gray area represents decorative shapes)
The three L-shaped patterns and the decorative shapes are all placed within the grid and must fill the grid completely. The horizontal and vertical strokes of the "L" can be of any length, but the length must be greater than 0 (i.e., it cannot degenerate into a line segment). Additionally, to make the L-shaped patterns distinct and easy to identify, the designers have specified that the three L-shaped patterns cannot overlap or intersect with each other. Naturally, the L-shaped patterns also cannot pass through or overlap with the decorative shapes.
Now that the designers have determined the positions of all decorative shapes, you are asked to calculate the total number of different logos that can be designed by placing the three L-shaped patterns.
Input
The first line of the input contains two space-separated positive integers $n$ and $m$, representing the number of rows and columns of the grid, respectively.
The next $n$ lines each contain $m$ characters, which are either "." or "#". "#" indicates that the cell contains a decorative shape, and "." indicates an empty area where an L-shaped pattern can be placed.
Output
Output a single integer representing the total number of possible logos.
Examples
Input 1
4 4 .... #... .... ..#.
Output 1
4
Note
There are only these 4 types of logos that satisfy the requirements. Note that the colors are only for illustration and do not affect the number of schemes, as in the actual logo, the three L-shaped patterns will use the same color, texture, and luster.
Constraints
- For 30% of the data, $n, m \le 5$
- For 100% of the data, $2 \le n, m \le 30$