Taco Grid Paths

You are given a grid with N rows and M columns. Each cell in the grid is either empty (represented by .) or blocked (represented by #). You start at the top-left corner of the grid and your goal is to reach the bottom-right corner. You may only move either to the right or down from any cell.

Determine the number of different paths from the top-left to the bottom-right cell, taking into account that some cells may be blocked. Since the number of ways can be very large, output the result modulo \(10^9+7\).

Input Format: The first line contains two integers \(N\) and \(M\). Each of the following \(N\) lines contains a string of length \(M\) representing a row of the grid.

Output Format: Output a single integer, the number of ways to reach the bottom-right cell modulo \(10^9+7\). If the starting or ending cell is blocked, the answer is 0.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two space-separated integers, \(N\) and \(M\), representing the number of rows and columns of the grid.
• The next \(N\) lines each contain a string of length \(M\) consisting of characters "." and "#", representing the grid.

outputFormat

Print a single integer to stdout: the number of ways to reach the bottom-right corner from the top-left corner, modulo \(10^9+7\).

3 3
...
...
...

6