문제

Author: Goran Žužić

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 a R × S grid. Some cells are not suitable for placing water pipes. 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 the following 6 pipe types:

Find the number of ways that pipes can be placed to connect the two locations with a 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 ≤ R, S ≤ 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..

예제 입력 1

2 3
...
.#.

예제 출력 1

1

예제 입력 2

3 3
...
...
...

예제 출력 2

12