Bessie has become an artist and is creating paintings of caves! Her current work in progress is a grid of height [Math Processing Error] such that each row of the grid contains exactly [Math Processing Error] squares ([Math Processing Error]). Each square is either empty, filled with rock, or filled with water. Bessie has already painted the squares containing rock, including the entire border of the painting. She now wants to fill some empty squares with water such that if the painting were real, there would be no net motion of water. Define the height of a square in the [Math Processing Error]-th row from the top to be [Math Processing Error]. Bessie wants her painting to satisfy the following constraint:
Suppose that square [Math Processing Error] is filled with water. Then if there exists a path from [Math Processing Error] to square [Math Processing Error] using only empty or water squares that are not higher than [Math Processing Error] such that every two adjacent squares on the path share a side, then [Math Processing Error] is also filled with water.

Find the number of different paintings Bessie can make modulo [Math Processing Error]. Bessie may fill any number of empty squares with water, including none or all.

The first line contains two space-separated integers [Math Processing Error] and [Math Processing Error].
The next [Math Processing Error] lines of input each contain [Math Processing Error] 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 '#'.

A single integer: the number of paintings satisfying the constraint modulo [Math Processing Error].

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

9