P2595 [ZJOI2009] Dominoes

There is an $n \times m$ rectangular grid with some cells blocked by obstacles. You need to place some $1 \times 2$ or $2 \times 1$ dominoes on this grid so that any two dominoes do not overlap, and no domino covers an obstacle. Moreover, for every pair of adjacent rows, there must be at least one domino crossing them; similarly, for every pair of adjacent columns, there must be at least one domino crossing them. Find the number of different placement methods. Note that you do not need to cover all unobstructed cells.

The first line contains two integers $n, m$. The next $n$ lines each contain $m$ characters describing the grid. Character `x` means the cell has an obstacle, and character `.` means the cell is empty.

Output a single integer: the number of different placements modulo $19\,901\,013$.

Sample explanation: Two valid placements are: ```plain 112 411 4.2 4.2 433 332 ``` Note that the digits are only used to distinguish dominoes; different labelings do not represent different solutions. Constraints: - For $40\%$ of the testdata, $n, m \leq 8$. - For $90\%$ of the testdata, $n, m \leq 14$. - For $100\%$ of the testdata, $1 \leq n, m \leq 15$. Translated by ChatGPT 5