P7642 [BalticOI 2006] JUMP THE BOARD! (Day 2)

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.

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$.

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

#### 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](https://www.cs.helsinki.fi/group/boi2006/) [Day 2: Jump](https://www.cs.helsinki.fi/group/boi2006/tasks/jump.pdf). Translated and organized by @[求学的企鹅](/user/271784). Translated by ChatGPT 5