Count the Number of Paths in a Labyrinth

You are given a labyrinth represented by a binary grid with 0 indicating open cells and 1 indicating traps. Your task is to count the number of distinct paths from the entrance at the top-left cell to the exit at the bottom-right cell. You are allowed to only move either right or down.

If either the starting cell or the destination cell is a trap, then there is no valid path and the answer is 0.

The solution uses the following recurrence formula in a dynamic programming approach:

\( dp[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = 1 \\ (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0), & \text{if } grid[i][j] = 0 \end{cases} \)

Here, \( dp[i][j] \) denotes the number of ways to reach cell \( (i, j) \) from the start.

inputFormat

The first line contains two integers \( r \) and \( c \) representing the number of rows and columns of the grid. This is followed by \( r \) lines, each containing \( c \) space-separated integers (either 0 or 1) representing the cells of the grid.

outputFormat

Output a single integer representing the number of distinct paths from the entrance to the exit.

## sample

3 3
0 0 1
0 0 1
1 0 0

2

</p>