Unique Paths in a Grid with Obstacles

You are given a grid with dimensions m × n. Each cell is either free (denoted by 0) or has an obstacle (denoted by 1). Your task is to calculate the number of unique paths from the top-left corner to the bottom-right corner while only moving either down or right and avoiding obstacles.

The starting cell is at the top-left (i.e. cell (1,1)) and the destination is at the bottom-right (i.e. cell (m,n)). If there is an obstacle at the starting or ending cell, then the answer is 0.

The recurrence used to solve the problem can be formulated in LaTeX as follows:

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

Your solution should read input from stdin and print the result to stdout.

inputFormat

The first line contains two space-separated integers m and n, representing the number of rows and columns respectively. The following m lines each contain n space-separated integers (either 0 or 1), representing the grid.

For example:

3 3
0 0 0
0 1 0
0 0 0

outputFormat

Output a single integer representing 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