Distinct Paths in a Grid with Obstacles

Alice is playing a grid-based game where she must navigate from the top-left corner (1, 1) to the bottom-right corner (n, m) of a grid. The grid contains obstacles represented by the character '#' that Alice cannot step on, while free cells are represented by '.'. In each move, she can only move either right or down.

Your task is to determine the number of distinct paths she can take to reach her destination. Since the number of paths can be very large, output the answer modulo $10^9+7$.

Note: If the start or the finish cell is blocked, the answer is 0.

inputFormat

The input is given via standard input (stdin). The first line contains two integers n and m, representing the number of rows and columns respectively. The following n lines each contain a string of m characters. Each character is either '.' (an empty cell) or '#' (an obstacle).

outputFormat

Output a single integer to standard output (stdout), which is the number of distinct paths from the top-left corner to the bottom-right corner modulo $10^9+7$.## sample

3 3
...
.#.
...

2