Unique Paths with Obstacles

Alice is exploring the number of unique paths in a rectangular grid with obstacles. The grid is an \( m \times n \) matrix, where each cell can either be empty (denoted as 0) or have an obstacle (denoted as 1). Starting from the top-left corner, Alice can only move either right or down. The goal is to reach the bottom-right corner of the grid. However, if any cell along the only path (or starting/ending cell) is blocked, the path is invalid.

Your task is to compute the number of unique paths from the top-left to the bottom-right corner avoiding obstacles. Note that if the starting cell \( (0, 0) \) or the ending cell \( (m-1, n-1) \) is an obstacle, the answer is 0.

The movement is constrained as follows:

• At each step, you can move right or down only.

Find the number of unique paths that satisfy the above conditions.

inputFormat

The first line contains two space-separated integers \( m \) and \( n \), representing the number of rows and columns of the grid, respectively. The following \( m \) lines each contain \( n \) integers (each either 0 or 1) separated by spaces, representing the grid.

For example, a 3x3 grid might look like:

3 3
0 0 0
0 1 0
0 0 0

outputFormat

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

For the example above, the output should be:

2

## sample

3 3
0 0 0
0 1 0
0 0 0

2