Pascal's Travels

You are given an $n \times n$ board. Each square holds a single nonnegative digit from $0$ to $9$.

You start on the top-left square and want to reach the bottom-right square. The digit written on the square you are currently on is the exact length of your next step: from a square holding the value $d$ you may move either $d$ squares to the right or $d$ squares down. A move that would leave the board is not allowed, and every move must go to the right or down. A square containing $0$ is a dead end, because a step of length $0$ makes no progress.

Count how many distinct paths lead from the top-left square to the bottom-right square.

The input describes between $1$ and $30$ boards and ends with a line containing only $-1$.

Each board begins with a line containing a single integer $n$ ($4 \le n \le 34$), the number of rows (and columns) of the board. The next $n$ lines each contain $n$ digits (each from $0$ to $9$) with no spaces between them.

For each board, print a single line containing one integer: the number of distinct paths from the top-left square to the bottom-right square. For every board this count is smaller than $2^{63}$.

Examining every path by brute force will likely exceed the time limit, so use dynamic programming instead. Every answer fits in a signed 64-bit integer (for example, long in Java or long long in C/C++).