Guards In The Storehouse
Contest: Educational Codeforces Round 27
Difficulty rating: 2500
Tags: bitmasks, dp

Polycarp owns a shop in the capital of Berland. Recently the criminal activity in the capital increased, so Polycarp is thinking about establishing some better security in the storehouse of his shop.

The storehouse can be represented as a matrix with n rows and m columns. Each element of the matrix is either . (an empty space) or x (a wall).

Polycarp wants to hire some guards (possibly zero) to watch for the storehouse. Each guard will be in some cell of matrix and will protect every cell to the right of his own cell and every cell to the bottom of his own cell, until the nearest wall. More formally, if the guard is standing in the cell (x0, y0), then he protects cell (x1, y1) if all these conditions are met:

- (x1, y1) is an empty cell;
- either x0 = x1 and y0 ≤ y1, or x0 ≤ x1 and y0 = y1;
- there are no walls between cells (x0, y0) and (x1, y1). There can be a guard between these cells, guards can look through each other.

Guards can be placed only in empty cells (and can protect only empty cells). The plan of placing the guards is some set of cells where guards will be placed (of course, two plans are different if there exists at least one cell that is included in the first plan, but not included in the second plan, or vice versa). Polycarp calls a plan suitable if there is not more than one empty cell that is not protected.

Polycarp wants to know the number of suitable plans. Since it can be very large, you have to output it modulo 109 + 7.

Input format:
The first line contains two numbers n and m — the length and the width of the storehouse (1 ≤ n, m ≤ 250, 1 ≤ nm ≤ 250).

Then n lines follow, ith line contains a string consisting of m characters — ith row of the matrix representing the storehouse. Each character is either . or x.

Output format:
Output the number of suitable plans modulo 109 + 7.

Constraints:
Time limit: 1.5 s
Memory limit: 512.0 MB

Note:
In the first example you have to put at least one guard, so there are three possible arrangements: one guard in the cell (1, 1), one guard in the cell (1, 3), and two guards in both these cells.

Example input:
1 3
.x.

Example output:
3

Example input:
2 2
xx
xx

Example output:
1

Editorial:
This problem can be solved using dynamic programming with broken profile. First of all, we have to make the number of rows not larger than 15; if it is larger, then we can just rotate the given matrix.
Let's fill the matrix from left to right, and in each column from top to bottom. Let dp[pos][mask][f1][f2] be the number of ways to achieve the following situation: we now want to fill cell with index pos, mask denotes the rows which are already protected in this column (so there is a wall in this row or there is a guard to the left), f1 is a flag that denotes if current cell is protected by some guard above, and f2 is a flag that denotes if there was a cell that was not protected.
When advancing from one column to another, we have to change the mask so we update the rows that are currently protected. The rows such that in the previous column there was a wall in this row become un-protected, and the rows such that there is a wall in current column in this row become protected. And, of course, f1 becomes zero.
When we place a guard, we set f1 to one and make the corresponding row protected. And when we are at the wall, we have to set f1 to zero, so the guard from above doesn't protect next cell.
The answer is the sum of all dp[n·m][whatever][whatever][whatever] values.