Cave Paintings#10439
Bessie has become an artist and is creating paintings of caves! Her current work in progress is a grid of height , with exactly squares in each row. Each square is either empty, filled with rock, or filled with water. Bessie has already painted all the squares containing rock, including the entire border of the painting. She now wants to fill some of the empty squares with water so that, if the painting were real, there would be no net movement of water.
Define the height of a square in the -th row from the top to be n + 1 - i. Bessie wants her painting to satisfy the following constraint:
Suppose that square is filled with water. If there exists a path from to a square using only empty or water-filled squares whose height is no greater than that of , and every two consecutive squares on the path share a side, then must also be filled with water.
Find the number of different paintings Bessie can create modulo 10^9 + 7. Bessie may fill any number of empty squares with water, including none or all of them.
The first line contains two space-separated integers and m~(1 \le n, m \le 1000).
Each of the next lines contains characters. Each character is either '' or '#', representing an empty square and a square filled with rock, respectively. The first and last rows, as well as the first and last columns, contain only '#'.
Print one integer: the number of paintings satisfying the constraint, modulo 10^9 + 7.
If any square in the second row is filled with water, then all empty squares must also be filled with water. Otherwise, suppose that no squares in the second row are filled with water. Then Bessie can independently choose whether or not to fill each of the three horizontally contiguous regions of empty squares in the third row with water. Thus, the total number of paintings is 1 + 2^3 = 9.
Example 1