Distinct Paths in a Grid with Obstacles

You are given a grid of size \(N \times N\) where each cell is either free (represented by 0) or blocked (represented by 1). Your task is to compute the number of distinct paths from the top-left cell (0,0) to the bottom-right cell (\(N-1, N-1\)) while only moving either down or right. A path is valid if it does not pass through any blocked cell.

The recurrence relation for computing the number of paths can be written in \(\LaTeX\) as:

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

Note that if the starting or ending cell is blocked, there is no valid path, and the answer is 0.

inputFormat

The first line of the input contains an integer \(N\) representing the size of the grid. Each of the next \(N\) lines contains \(N\) space-separated integers (either 0 or 1) representing the grid. A value of 0 indicates a free cell, while 1 indicates an obstacle.

For example:

3
0 0 0
0 1 0
0 0 0

outputFormat

Output a single integer - the number of distinct paths from the top-left to the bottom-right cell under the given constraints.

## sample

3
0 0 0
0 1 0
0 0 0

2