There is an $n \times m$ rectangular grid, some positions of which contain obstacles. We want to place some $1 \times 2$ or $2 \times 1$ dominoes in this grid such that no two dominoes overlap, and no domino is placed on an obstacle. Additionally, the placement must satisfy the condition that there is at least one domino spanning across every two adjacent rows, and at least one domino spanning across every two adjacent columns. Find the number of different ways to place the dominoes. Note that you do not need to cover all non-obstacle cells.

Input

The first line contains two integers $n, m$. The next $n$ lines each contain $m$ characters, representing the rectangular grid. The character "x" indicates an obstacle at that position, and the character "." indicates no obstacle.

Output

A single integer representing the number of different placement methods modulo $19901013$.

Examples

Input 1

3 3
...
...
...

Output 1

2

Note

The two placement methods are:

112 411
4.2 4.2
433 332

Note that the numbers here are only used to distinguish the dominoes; different permutations do not represent different solutions.

Constraints

For 40% of the data, $1 \le n, m \le 8$. For 90% of the data, $1 \le n, m \le 14$. For 100% of the data, $1 \le n, m \le 15$.