Unique Paths in a Grid with Obstacles

You are given an ( n \times m ) grid where each cell can either be passable (represented by 0) or blocked (represented by 1). Your task is to determine the number of unique paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,m)). You can only move right or down at any step. Note that if the starting or ending cell is blocked, then no path exists.

Formally, let ( grid[i][j] ) denote the cell value at row ( i+1 ) and column ( j+1 ). A valid move is from ( grid[i][j] ) to either ( grid[i+1][j] ) (down) or ( grid[i][j+1] ) (right), provided the target cell is passable (0). Compute the total number of unique paths from the top-left to the bottom-right cell.

inputFormat

The input is given via standard input (stdin). The first line contains two integers ( n ) and ( m ) ( (1 \leq n,m \leq 100)), representing the number of rows and columns respectively. The following ( n ) lines each contain ( m ) integers (either 0 or 1) separated by spaces indicating the grid cells.

outputFormat

Output a single integer representing the number of unique paths from the top-left to the bottom-right corner of the grid. The output should be printed to standard output (stdout).## sample

3 3
0 0 0
0 1 0
0 0 0

2