Counting Paths in a Grid

You are given an n x n grid where each cell is either passable (1) or an obstacle (0). Your task is to determine the number of distinct paths from the top-left corner to the bottom-right corner, moving only right or down.

The recurrence relation used to determine the number of paths is given by the formula:
$$ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j] + \text{dp}[i][j-1] & \text{if } grid[i][j] = 1, \\ 0 & \text{if } grid[i][j] = 0. \end{cases} $$
with the initial condition dp[0][0] = 1 if the starting cell is passable. If the destination is unreachable, output 0.

inputFormat

The first line contains a single integer n, indicating the size of the grid. This is followed by n lines, each containing n space-separated integers (0 or 1) representing the grid.

outputFormat

Output a single integer representing the number of distinct paths from the top-left corner to the bottom-right corner.## sample

3
1 1 1
1 0 1
1 1 1

2