Mirko, the mad plumber, was hired to construct a water supply network between two locations in a city. The city map can be represented as an \(R \times S\) grid. Some cells are not suitable for placing water pipes. The locations Mirko needs to connect are placed directly above the top-left cell of the grid, and directly below the bottom-right cell.

Each suitable cell Mirko can either leave empty or use it for placing one of \(6\) pipe types: the \(4\) elbow (corner) pieces, each joining two of the cell's sides at a right angle, and the \(2\) straight pieces (one horizontal, one vertical).

Find the number of ways that pipes can be placed to connect the two locations with a single continuous pipe (water must not be spilled). All placed pipe parts must be in use.

Output the solution modulo \(10007\).

The first line of input contains the integers \(R\) and \(S\) (\(2 \le R, S \le 10\)), the number of rows and columns of the city grid, respectively. Each of the next \(R\) lines contains exactly \(S\) characters: . if the cell is suitable for placing pipes, and # if not.

The first and only line of output must contain the required number of ways modulo \(10007\).

riseoj 작성

출처 COCI 2010/2011 Contest 6