Unique Paths in a Grid with Obstacles

You are given a grid of size m × n where each cell is either a passable cell (denoted by 0) or an obstacle (denoted by 1). Your task is to determine the number of unique paths from the top-left corner to the bottom-right corner. You can only move either down or right at any step.

If we denote the number of rows by \(m\) and the number of columns by \(n\), then for a grid without obstacles, the total number of unique paths is given by the binomial coefficient \(\binom{m+n-2}{m-1}\). However, obstacles will block some paths. If the start or end cell is blocked, the number of paths is zero.

Write a program to compute the number of such unique paths.

inputFormat

The first line of input contains two integers \(m\) and \(n\) separated by a space, representing the number of rows and columns in the grid, respectively. The next \(m\) lines each contain \(n\) integers (either 0 or 1) separated by spaces, representing the grid. The value 0 indicates a passable cell and 1 indicates an obstacle.

outputFormat

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

3 3
0 0 0
0 0 0
0 0 0

6