## USACO 2020 January Contest, Platinum

## Problem 1. Cave Paintings

Contest has ended.

**Log in to allow submissions in analysis mode**

Suppose that square $a$ is filled with water. Then if there exists a path from $a$ to square $b$ using only empty or water squares that are not higher than $a$ such that every two adjacent squares on the path share a side, then $b$ is also filled with water.

Find the number of different paintings Bessie can make modulo $10^9+7$. Bessie may fill any number of empty squares with water, including none or all.

#### SCORING:

- Test cases 1-5 satisfy $N,M\le 10.$
- Test cases 6-15 satisfy no additional constraints.

#### INPUT FORMAT (file cave.in):

The first line contains two space-separated integers $N$ and $M$.The next $N$ lines of input each contain $M$ characters. Each character is either '.' or '#', representing an empty square and a square filled with rock, respectively. The first and last row and first and last column only contain '#'.

#### OUTPUT FORMAT (file cave.out):

A single integer: the number of paintings satisfying the constraint modulo $10^9+7$.#### SAMPLE INPUT:

4 9 ######### #...#...# #.#...#.# #########

#### SAMPLE OUTPUT:

9

If a square in the second row is filled with water, then all empty squares must be filled with water. Otherwise, assume that no such squares are filled with water. Then Bessie can choose to fill any subset of the three horizontally contiguous regions of empty squares in the third row. Thus, the number of paintings is equal to $1+2^3=9.$

Problem credits: Daniel Zhang