Distinct Paths in a Grid

Given an n × m grid represented by integers where 0 indicates an empty cell and 1 indicates an obstacle, compute the number of distinct paths from the top-left corner to the bottom-right corner. You can only move either to the right or down at any point in time.

If a cell is an obstacle, it cannot be part of a valid path. Let \(dp[i][j]\) denote the number of ways to reach cell \( (i, j) \). In cells without obstacles, the recurrence is given by:

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

with the boundary conditions appropriately defined.

If there is no valid path (or when the grid is empty), output 0.

inputFormat

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

outputFormat

Output a single integer: the number of distinct paths from the top-left cell to the bottom-right cell of the grid.## sample

3 3
0 0 0
0 1 0
0 0 0

2