DOMINO2 - Domino
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
Added by: | Bin Jin |
Date: | 2009-03-30 |
Time limit: | 3s |
Source limit: | 10000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 CPP |
Resource: | Zhejiang TSC for Chinese National OI 2009 |