Unique Paths with Obstacles

In this problem, you are given an ( n \times m ) grid where each cell is either open (represented by '.') or blocked (represented by 'X'). You need to determine the number of distinct paths from the top-left corner to the bottom-right corner of the grid, moving only down or right, and avoiding blocked cells. The answer should be computed modulo (10^9+7).

More formally, let ( dp[i][j] ) denote the number of ways to reach cell ( (i,j) ). The recurrence is given by:
[ dp[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = 'X' \ dp[i-1][j] + dp[i][j-1], & \text{otherwise} \end{cases} ] with the starting condition ( dp[0][0]=1 ) if the starting cell is open, otherwise (0).

inputFormat

The first line contains two space-separated integers ( n ) and ( m ) representing the number of rows and columns in the grid, respectively. This is followed by ( n ) lines, each containing a string of length ( m ) consisting of the characters '.' and 'X', representing the grid.

outputFormat

Output a single integer representing the number of distinct paths from the top-left to the bottom-right corner, computed modulo (10^9+7).## sample

3 3
.X.
...
X..

2