Problem Background

ural 1519
A problem from Chen Danqi's "Dynamic Programming Problems Based on Connectivity State Compression".

Problem Description

Given an $n \times m$ grid, some cells cannot be used for laying lines, while others must be used to form a closed circuit. How many ways are there to lay the lines?

Input Format

The first line contains two integers, representing $n$ and $m$ respectively.

From the second line to the $(n+1)$-th line, each line contains a string of length $m$ consisting only of * and ., where * indicates a cell that cannot be used for laying lines, and . indicates a cell that must be used.

Output Format

Output a single integer, representing the total number of ways.

Sample Input and Output

Sample Input #1

4 4
**..
....
....
....

Sample Output #1

2

Sample Input #2

4 4
....
....
....
....

Sample Output #2

6

Notes

Data Size and Constraints

• For $100\%$ of the data, it is guaranteed that $2 \le n, m \le 12$.

见题面 Input 部分

见题面 Output 部分