Game Board Jump Counting

We are given an (n \times n) game board filled with non-negative integers. Each cell contains a number that represents the jump length from that cell. A move from a cell can only be made to the right or downward by exactly the number specified in that cell. If a jump would lead outside the board, it is considered illegal. Note that a cell with value (0) is a dead end and prevents any further moves. The task is to compute the total number of legal paths from the top-left corner (start) to the bottom-right corner (destination).

For example, in a (4 \times 4) board, if there are three legal paths from the start to the destination, the answer would be 3.

inputFormat

The first line contains an integer (n), the size of the board. Each of the following (n) lines contains (n) space-separated non-negative integers representing the board.

outputFormat

Output a single integer representing the total number of legal paths from the top-left corner to the bottom-right corner of the board.

sample

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

3