Unique Paths with Obstacles

Given a grid of size \(m \times n\) where each cell is either free (0) or blocked (1), determine the number of unique paths for a robot to move from the top-left cell to the bottom-right cell, only moving either right or down. The robot cannot pass through obstacles.

Note: If either the starting cell or the ending cell is blocked, then there is no valid path.

inputFormat

The input is read from standard input. The first line contains two integers (m) and (n), representing the number of rows and columns of the grid. Each of the next (m) lines contains (n) space-separated integers (0 or 1), where 0 indicates a free cell and 1 indicates an obstacle.

outputFormat

Print a single integer representing the number of unique paths from the top-left to the bottom-right cell.## sample

3 3
0 0 0
0 1 0
0 0 0

2