P6008 [USACO20JAN] Cave Paintings P

Bessie has become an artist and is painting a mural. The painting is a square grid of height $N$, and each row contains $M$ cells ($1\le N,M\le 1000$). Each cell is either empty, painted as rock, or painted as water. Bessie has already painted all rock cells, including the entire border of the painting. She now wants to paint water in some of the empty cells so that, if the painting were real, there would be no net movement of water. Define the height of a cell in row $i$ (counting from top to bottom) as $N+1-i$. Bessie wants her painting to satisfy the following rule: Suppose cell $a$ is painted as water. Then if there exists a path from $a$ to a cell $b$, consisting only of empty cells or water cells whose heights are not greater than the height of $a$, where each pair of consecutive cells on the path shares a common edge, then $b$ is also painted as water. Find the number of different paintings Bessie can create, modulo $10^9+7$. Bessie may paint water in any number of empty cells, including painting none or painting all.

The first line contains two space-separated integers $N$ and $M$. The next $N$ lines each contain $M$ characters. Each character is `.` or `#`, representing an empty cell and a rock cell, respectively. The first and last row, and the first and last column, contain only `#`.

Output one integer: the number of paintings that satisfy the rule, modulo $10^9+7$.

### Sample Explanation If any cell in the second row is painted as water, then all empty cells must be painted as water. Otherwise, suppose no cell in the second row is painted as water. Then Bessie may choose any subset of the three connected empty regions in the third row to paint as water. Therefore, the total number of paintings is $1+2^3=9$. ### Subtasks - Test cases $1 \sim 5$ satisfy $N,M \leq 10$. - Test cases $6 \sim 15$ have no additional constraints. Translated by ChatGPT 5