Unique Paths with Obstacles

You are given an n × m grid, where each cell is either free (represented by 0) or blocked by an obstacle (represented by 1). A robot starts at the top-left corner and needs to reach the bottom-right corner of the grid. The robot can only move either down or right at any step.

Your task is to calculate the number of unique paths from the start to the finish. If the starting or ending cell contains an obstacle, then no valid path exists.

The recurrence relation for a cell without an obstacle is given by:

$$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$

where the additions only count from cells that are within the grid bounds and are not blocked by obstacles.

inputFormat

The input consists of multiple test cases. For each test case:

• The first line contains two integers n and m (separated by a space), representing the number of rows and columns of the grid.
• This is followed by n lines, each containing m integers (0 or 1) separated by spaces, representing the grid.

The sequence of test cases is terminated by a line containing a single 0.

Note: All input is provided via standard input (stdin).

outputFormat

For each test case, output a single integer on a new line representing the number of unique paths from the top-left corner to the bottom-right corner.

Note: All output should be sent to standard output (stdout).

## sample

3 3
0 0 0
0 1 0
0 0 0
0

2