Unique Paths in a Grid With Obstacles

You are given a grid with n rows and m columns. Each cell in the grid contains either a 0 or a 1, where 0 represents a passable cell and 1 represents a blocked cell.

Your task is to determine the number of unique paths from the top-left corner to the bottom-right corner of the grid. From any cell, you can only move right or down to the next cell. If either the starting cell (top-left) or the destination cell (bottom-right) is blocked, the answer is 0.

A dynamic programming approach is suggested where the recurrence relation is given by: $$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$ if cell \((i,j)\) is passable. Otherwise, if the cell is blocked, no paths pass through it.

inputFormat

The first line contains two space-separated integers: n (the number of rows) and m (the number of columns).

The next n lines each contain m space-separated integers (each either 0 or 1) representing the grid.

outputFormat

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

## sample

3 3
0 0 0
0 0 0
0 0 0

6

</p>