Counting Valid Paths in a Grid with Obstacles

You are given a grid with N rows and M columns. Each cell in the grid is either open (0) or blocked (1). Your task is to determine the number of valid paths from the top-left corner to the bottom-right corner, moving only down or right at each step.

If either the starting cell (top-left) or the destination cell (bottom-right) is blocked, the answer is 0.

The number of paths can be computed using dynamic programming with the recurrence formula: $$ dp[i][j] = dp[i-1][j] + dp[i][j-1] $$ where the cell \( (i,j) \) is not blocked. The problem constraints ensure that \(1 \leq N, M \leq 100\).

inputFormat

The first line contains two integers N and M, the number of rows and columns of the grid. Each of the next N lines contains M integers (either 0 or 1) separated by spaces representing the grid. A 0 indicates a free cell and a 1 indicates an obstacle.

outputFormat

Output a single integer representing the number of valid paths from the top-left corner to the bottom-right corner. The output should be terminated by a newline character.

## sample

3 3
0 0 0
0 1 0
0 0 0

2

</p>