Unique Paths with Obstacles

Given a 2D grid where each cell is either empty (represented by 0) or an obstacle (represented by 1), compute the number of unique paths from the top-left corner to the bottom-right corner. You can only move either downward or rightward at any point in time.

If the starting cell or ending cell has an obstacle, or if there is no valid path, return 0.

Mathematically, let \(dp[i][j]\) denote the number of ways to reach cell \((i,j)\). Then the recurrence is given by:

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

Note: The first row and first column need special handling due to only one possible path (if no obstacles).

inputFormat

The input is read from the standard input. The first line contains two integers \(m\) and \(n\) indicating the number of rows and columns of the grid. Each of the following \(m\) lines contains \(n\) integers separated by spaces, each representing a cell in the grid (0 for an empty space and 1 for an obstacle).

For example, the input for a 3x3 grid might be:

3 3
0 0 0
0 1 0
0 0 0

outputFormat

Output the number of unique paths from the top-left corner to the bottom-right corner. The output is written to the standard output.

For the example above, the correct output is:

2

## sample

3 3
0 0 0
0 1 0
0 0 0

2