P5056 [Template] Plug DP.

ural 1519. An example problem from Chen Danqi’s article *Dynamic Programming Problems Based on Connectivity State Compression*.

Given an $n\times m$ grid, some cells cannot be used to place lines, and all other cells must be used to place lines, forming one closed loop. How many different ways are there to place the lines?

The first line contains two integers, representing $n$ and $m$. From the second line to the $(n+1)$-th line, each line contains a string of length $m$ consisting only of `*` and `.`, where `*` means you cannot place lines in this cell, and `.` means you must place lines in this cell.

Output one line with one integer, representing the total number of valid ways.

#### Constraints - For $100\%$ of the testdata, $2\le n,m\le 12$. Translated by ChatGPT 5