Unique Paths with Obstacles

You are given an $n \times n$ grid where each cell is either 0 (empty) or 1 (an obstacle). A robot starts at the top-left corner (cell (0, 0)) and must reach the bottom-right corner (cell (n-1, n-1)). The robot can only move either down or right at any point in time. Your task is to calculate the number of unique paths the robot can take to reach its destination.

Note: If the starting cell or the ending cell is blocked by an obstacle, then no valid paths exist.

The problem can be formulated using dynamic programming. The recurrence relation is:

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

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n (the size of the grid).
• Each of the following n lines contains n space-separated integers, each being either 0 or 1, representing a row of the grid.

0 represents an empty cell and 1 represents an obstacle.

outputFormat

Output a single integer to stdout, which is the number of unique paths from the top-left to the bottom-right corner of the grid.

## sample

3
0 0 0
0 1 0
0 0 0

2

</p>