Count Distinct Paths in a Grid

You are given a 2D grid with $n$ rows and $m$ columns. Each cell of the grid contains either a 0 or a 1, where 0 represents a free cell and 1 represents an obstacle. A robot starts at the top-left cell (first row, first column) and needs to reach the bottom-right cell (last row, last column). The robot can only move either down or right at any step. Your task is to calculate the number of distinct paths from the start to the destination. If the start or destination is blocked, or if there is no valid path, the output should be 0.

The transition formula for dynamic programming is given by:

$$dp[i][j] = \begin{cases} 0 & \text{if } grid[i][j] = 1, \\ dp[i-1][j] + dp[i][j-1] & \text{if } grid[i][j] = 0 \end{cases} $$

Note that $dp[0][0]=1$ if the starting cell is free. Use this recurrence relation to fill up the dp table and find the number of valid paths to reach the bottom-right cell.

inputFormat

The first line of the input contains two integers $n$ and $m$, representing the number of rows and columns respectively. Each of the following $n$ lines contains $m$ space-separated integers (either 0 or 1), which represent the cells of the grid.

outputFormat

Output a single integer representing the number of distinct paths from the top-left corner to the bottom-right corner. The result should be printed to stdout.## sample

3 3
0 0 0
0 1 0
0 0 0

2

</p>