Unique Paths with Obstacles

You are given a grid of size n × m. Each cell in the grid is either free (denoted by '.') or blocked by an obstacle (denoted by '#'). Your task is to compute the number of unique paths from the top-left corner to the bottom-right corner, where you can only move either right or down at any step. If either the starting cell or the destination cell is blocked, then there is no valid path and the answer is 0.

The problem can be solved using dynamic programming. Let \(dp[i][j]\) represent the number of ways to reach cell \((i, j)\). The state transition is given by:

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

with the base case \(dp[0][0] = 1\) (provided that \(grid[0][0] = '.'\)).

inputFormat

The first line of input 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 that describes a row of the grid. Each character in the string is either '.' (a free cell) or '#' (an obstacle).

outputFormat

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

## sample

3 3
...
.#.
...

2