Unique Paths in a Grid with Obstacles

You are given a grid with n rows and m columns. Each cell in the grid is either empty (represented by 0) or an obstacle (represented by 1). Your task is to determine the number of unique paths from the top-left corner (cell (0, 0)) to the bottom-right corner (cell (n-1, m-1)) such that you can only move either right or down at any step, and you cannot move through obstacles.

If the starting cell or the destination cell is an obstacle, the answer is 0.

The dynamic programming recurrence used to calculate the number of paths is given by:

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

Consider the following examples:

• For the grid

  3 3
  0 0 0
  0 1 0
  0 0 0
      

  the number of unique paths is 2.
• For the grid

  2 2
  0 1
  1 0
      

  the number of unique paths is 0.

Note: The solution must read input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The first line of input contains two space-separated integers n and m representing the number of rows and columns in the grid.

Each of the next n lines contains m space-separated integers. Each integer is either 0 (representing an empty cell) or 1 (representing an obstacle).

It is guaranteed that 1 ≤ n, m ≤ 100, and each cell is either 0 or 1.

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