Domino Tiling with Obstacles and Coverage Constraints

Given an \(n \times m\) grid with obstacles, count the number of ways to place some \(1 \times 2\) or \(2 \times 1\) dominoes such that:

• No two dominoes overlap.
• No domino is placed on an obstacle.
• For every pair of adjacent rows (i.e. rows \(i\) and \(i+1\) for \(1 \le i < n\)), there is at least one vertical domino covering one cell from each row.
• For every pair of adjacent columns (i.e. columns \(j\) and \(j+1\) for \(1 \le j < m\)), there is at least one horizontal domino covering one cell from each column.

The dominoes can be placed arbitrarily (they do not have to cover all free cells). Compute the total number of valid placements.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of rows and columns.

Each of the next \(n\) lines contains a string of length \(m\) composed of characters '.' and '#' where '.' denotes an empty cell and '#' denotes an obstacle.

outputFormat

Output a single integer representing the number of valid domino placements.

sample

2 2
..
..

0