Water Resource Transportation

In an \( r \times s \) grid city, you are in charge of designing the transportation of water resources. Specifically, water must be transported from a point above the top‐left cell \( (1,1) \) to a point below the bottom‐right cell \( (r,s) \) by laying water pipes.

Each cell in the grid is either an obstacle or available for laying pipes. A cell containing a # represents an obstacle where no pipe can be laid, whereas a cell containing a . is available. In every available cell, you have the option to either leave it empty or lay exactly one pipe piece. There are six types of pipe pieces available, each connecting two of the four cardinal directions. The allowed pipe pieces are those connecting:

• Up and Down (vertical)
• Left and Right (horizontal)
• Up and Right
• Up and Left
• Down and Right
• Down and Left

The design must satisfy two conditions:

1. The water, entering from above cell \( (1,1) \), must flow through a single continuous pipeline without any leaks and exit below cell \( (r,s) \).
2. If a pipe is laid in a cell, it must be used in the pipeline (i.e. the pipeline passes through that cell and the pipe’s two endpoints exactly match the directions of entry and exit for that cell).

For example, the pipe laid in the source cell \( (1,1) \) must have a connection from the top (since water enters from above) and must connect to one other direction, either right or down (a connection to left would lead outside the grid). Similarly, in the destination cell \( (r,s) \), the pipe must have a connection to the bottom so that water may exit below.

Your task is to calculate the total number of valid design schemes modulo \(10007\).

inputFormat

The first line contains two integers \( r \) and \( s \) representing the number of rows and columns of the grid.

The following \( r \) lines each contain a string of length \( s \) composed of characters . and #. A . indicates an available cell where a pipe may be laid, and a # indicates an obstacle.

outputFormat

Output a single integer representing the number of valid design schemes modulo \( 10007 \).

sample

2 2
..
..

2