• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت

Super Mario, 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 $\times$ S grid. Some cells are not suitable for placing water pipes. Locations Mario needs to connect are placed directly above the top left cell of the grid, and directly below the bottom right cell.

Each suitable cell Mario can either \textbf{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.

Input

The first line of input contains the integers R and S, the number of rows and columns of the city grid, respectively. Each of the next R lines contains exactly S characters: ‘$\cdot$’ if the cell is suitable for placing pipes, and ‘#’ if not.

Output

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

Constraints

• $2 \leq R,S \leq 10$

Sample Test Data

input 1

3 3
...
...
...

output 1

12

input 2

3 2
...
.#.

output 2

1

Sample description

In the second sample, this is the only possible solution: