Unique Paths in a Grid with Obstacles

You are given an n x m grid where each cell is either empty (represented by a dot .) or blocked (represented by a hash #). The task is to determine the number of unique paths from the top-left corner (cell (1, 1)) to the bottom-right corner (cell (n, m)). You can only move either right or down at any step.

Note:

• If the start or end cell is blocked, then the answer is 0.
• The answer should be computed using dynamic programming. The transition can be described by the formula:

\(dp[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = '#' \\ dp[i-1][j] + dp[i][j-1], & \text{otherwise} \end{cases}\)

Here, \(dp[i][j]\) represents the number of ways to reach cell \((i+1, j+1)\) (using 0-indexing in the code), and you only add from the top and left cells if they exist.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) representing the number of rows and columns respectively.

Each of the next n lines contains a string of length m consisting of characters . and #. The character . represents an empty cell and # represents a blocked cell.

outputFormat

Output a single integer representing the number of unique paths from the top-left to the bottom-right corner of the grid. If no valid path exists, output 0.

## sample

2 2
..
..

2

</p>