Count Paths in a Grid

Given a grid consisting of n rows and m columns, where each cell is either free (denoted by .) or blocked (denoted by #), your task is to determine the number of distinct paths from the top-left corner to the bottom-right corner. In each step, you may only move right or down.

If either the starting cell or the destination cell is blocked, the answer will be 0. The answer must be computed modulo $$10^9+7$$.

This problem can be efficiently solved using a dynamic programming approach.

inputFormat

The input is read from standard input. The first line contains two integers n and m separated by a space, representing the number of rows and columns of the grid. This is followed by n lines, each containing a string of length m that describes a row of the grid.

outputFormat

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

3 3
...
.#.
...

2