Taco Paths

You are given an n × m grid consisting of two types of cells: a passable cell denoted by . and an obstacle denoted by #. Starting from the top-left cell (1, 1) and moving only to the right or down, your task is to determine the number of distinct paths to reach the bottom-right cell (n, m) without stepping on any obstacles.

Note that if either the starting or ending cell is blocked, there is no valid path. Since the number of paths may be very large, output the answer modulo \(10^9+7\).

inputFormat

The first line contains two integers, n and m (\(1 \le n, m \le 10^3\)), representing the number of rows and columns of the grid respectively. This is followed by n lines, each containing a string of length m comprised of characters . and #, where . indicates an open cell and # indicates an obstacle.

outputFormat

Output a single integer representing the number of distinct paths from the top-left to the bottom-right cell modulo \(10^9+7\). If no valid path exists, output 0.

3 3
...
.#.
...

2