Count Paths in a Grid with Obstacles

You are given a grid with N rows and M columns. Each cell is either . (free cell) or # (obstacle). Starting from the top-left cell (1, 1) and moving only right or down, you need to determine the number of distinct paths to reach the bottom-right cell (N, M) without stepping on an obstacle. If the starting or ending cell is an obstacle, the answer is 0.

As the answer can be very large, output it modulo \(10^9+7\).

Constraints: The input will be given via standard input and the output via standard output.

inputFormat

The input starts with two integers \(N\) and \(M\) representing the number of rows and columns in the grid. This is followed by \(N\) lines, each line containing a string of length \(M\) consisting of characters . and #, representing a free cell or an obstacle respectively.

Example:

3 3
... 
.#. 
... 

outputFormat

Output a single integer: the number of distinct paths from the top-left to the bottom-right cell modulo \(10^9+7\).

## sample

3 3
...
.#.
...

2

</p>