+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- 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: