Description

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.

Input Format

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 Format

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

3 3
...
...
...

2

Hint

Sample explanation:

Two valid placements are:

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