Description

An $n \times n$ game board is filled with integers, one non-negative integer in each cell. The goal is to jump from the top-left corner to the bottom-right corner along any valid path. The integer in any cell gives the jump length when leaving that cell. If a jump length would move you outside the board, then the jump in that specific direction is forbidden. All jumps must be either to the right or downward. Note that $0$ is a dead end and prevents any further progress.

As shown in Figure $1$, on the $4 \times 4$ board, the solid circle marks the start position and the dashed circle marks the target position. Figure $2$ shows three valid paths from the start to the target, and in each path the irrelevant numbers are removed.

Your task is to write a program to determine the number of valid paths from the top-left corner to the bottom-right corner.

Input Format

The first line contains a positive integer $n$, the number of rows and columns of the board. The next $n$ lines follow. Each line contains $n$ integers, and each integer is in the range $0 \cdots 9$.

Output Format

The only line contains one integer, the number of valid paths from the top-left corner to the bottom-right corner.

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

3

Hint

Constraints

• For $100\%$ of the testdata, $4 \le n \le 100$.
• The number of valid paths can be quite large. Using a $64$-bit integer variable (in C, long long int, in Pascal, Int64) can only get $70\%$ of the score. It is guaranteed that for all inputs, the number of paths can be written with no more than $100$ digits.

Notes

The problem comes from Baltic Olympiad in Informatics 2006 Day 2: Jump.
Translated and organized by @求学的企鹅.

Translated by ChatGPT 5