Counting Pipe Installations

Time limit2sMemory limit128 MB

Summary

Count the ways to lay a single connected pipe path with six pipe shapes from the top-left entry to the bottom-right exit through a grid with blocked cells, modulo 10007.

Level: Medium6 of 10
Topics: Dynamic programming, Matrix, Combinatorics
Solved: No attempts yet

Problem

A city is represented as an R x S grid. Each cell is either available for a pipe or unavailable.

You want to install pipes so that water flows from the point just above the upper-left cell to the point just below the lower-right cell.

An available cell may be left empty, or it may contain one of the following six pipe pieces.

Every pipe you install must be part of the actual water path, and water must not leak at any connection. Count the number of possible installations.

Input

The first line contains the city dimensions R and S. (2 <= R, S <= 10)

Each of the next R lines describes one row of the city. A '.' means that a pipe may be placed in that cell, and a '#' means that no pipe may be placed there.

Output

Print the number of possible pipe installations modulo 10007.

Examples2

Example 1
Input
```
2 3
...
.#.
```
Expected output
```
1
```
Example 2
Input
```
3 3
...
...
...
```
Expected output
```
12
```