You have an n × m rectangle, some cells have some obstacles in. A domino piece is a 1 × 2 or 2 × 1 rectangle. You're going to place some domino pieces in this rectangle so that there's no empty cell is covered more than once and no cell with obstacles is covered. For some unknown reason, you have to ensure there's at least one piece covering some cell in row i and some cell in row i+1 at the same time for all i in 1 ... n-1. Similarly there's at least one piece covering some cell in column i and column i+1 for all i in 1 ... m-1. Your task is to count the number of different valid domino covering.

Input

The first line of the input contains two integer numbers n, m (1 ≤ n, m ≤ 15).

The following n lines describe the rectangle. Each line contains m characters. The j-th character of line i+1 may be either a 'x' (ASCII code 120), representing obstacles in cell (i, j), or a '.' (ASCII code 46), representing an empty cell.

Output

One number, representing the number of different valid domino placing.

Since the number could be quite large, output the answer modulo 19901013.

Example

Input:
3 3
...
...
...

Output:
2

Note

The 2 different placings are

   112     411
   4.2     4.2
   433     332