Count Distinct Routes in a Grid

In this problem, you are given an n x n grid. The cells of the grid are either passable (denoted by 0) or impassable (denoted by 1). You need to determine the number of distinct routes from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1), moving only to the right or down, and without stepping into impassable cells.

The dynamic programming recurrence used to solve this is given by: [ \text{dp}[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = 1, \ \text{dp}[i-1][j] + \text{dp}[i][j-1], & \text{if } grid[i][j] = 0 \end{cases} ] with the initial condition (dp[0][0] = 1) (provided that the starting cell is passable) and making sure that any cell in the first row or first column gets its value only from its left or top neighbor respectively (if they are not blocked).

inputFormat

The input is given via stdin. The first line contains a single integer (n) ((1 \le n \le 1000)), representing the size of the grid. The next (n) lines each contain (n) integers separated by spaces (each integer is either 0 or 1), representing the grid. A 0 indicates a passable cell, while a 1 indicates an impassable cell.

outputFormat

Output a single integer representing the number of distinct routes from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1). The answer should be printed to stdout.## sample

3
0 0 0
0 1 0
0 0 0

2