Unique Paths in a Grid with Obstacles

You are given a grid with m rows and n columns. Each cell of the grid is either empty (represented by 0) or has an obstacle (represented by 1). You need to determine the number of unique paths from the top-left corner to the bottom-right corner of the grid, moving only right or down.

If the starting cell or ending cell is blocked by an obstacle, then there is no valid path. The number of paths can be computed using dynamic programming. The recurrence relation 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}$$

Here, \(dp[i][j]\) is the number of unique paths to reach cell \((i,j)\) from the start.

Your solution must read input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

The first line contains two integers m and n, representing the number of rows and columns of the grid respectively. The following m lines each contain n integers separated by spaces, where each integer is either 0 or 1. 0 indicates an empty cell and 1 indicates an obstacle.

For example:

3 3
0 0 0
0 1 0
0 0 0

outputFormat

Output a single integer that represents the number of unique paths from the top-left corner to the bottom-right corner of the grid.

## sample

3 3
0 0 0
0 1 0
0 0 0

2