파스칼의 여행

$n \times n$ 크기의 게임판이 주어진다. 각 칸에는 $0$부터 $9$까지의 한 자리 음이 아닌 정수가 하나씩 적혀 있다.

왼쪽 위 칸에서 출발하여 오른쪽 아래 칸으로 이동하는 것이 목표다. 현재 칸에 적힌 수는 다음에 이동해야 하는 정확한 걸음 수를 뜻한다. 즉, 값이 $d$인 칸에서는 오른쪽으로 $d$칸 또는 아래쪽으로 $d$칸 중 하나로만 이동할 수 있다. 이동한 결과가 게임판을 벗어난다면 그 방향으로는 이동할 수 없으며, 모든 이동은 오른쪽 또는 아래쪽으로만 향한다. 값이 $0$인 칸은 한 걸음도 나아갈 수 없으므로 막다른 곳이다.

왼쪽 위 칸에서 오른쪽 아래 칸까지 가는 서로 다른 경로의 수를 구하여라.

입력은 $1$개 이상 $30$개 이하의 게임판으로 이루어지며, $-1$만 적힌 줄로 끝난다.

각 게임판은 게임판의 행(그리고 열)의 개수를 나타내는 정수 $n$ ($4 \le n \le 34$)이 적힌 줄로 시작한다. 그 다음 $n$개의 줄에는 각각 $n$개의 숫자($0$부터 $9$까지)가 공백 없이 이어져 있다.

각 게임판마다 한 줄에 왼쪽 위 칸에서 오른쪽 아래 칸까지 가는 서로 다른 경로의 수를 정수로 출력한다. 모든 게임판에서 이 값은 $2^{63}$보다 작다.

모든 경로를 하나씩 확인하는 완전 탐색으로는 시간 제한을 초과하기 쉬우므로 동적 계획법을 사용하라. 모든 답은 부호 있는 64비트 정수에 들어간다(예: Java의 long, C/C++의 long long).