보드 점프

N × N 크기의 게임 보드가 있고, 각 칸에는 0부터 9까지의 숫자가 하나씩 적혀 있다. 말은 왼쪽 위 칸에서 출발하여 오른쪽 아래 칸까지 가는 것이 목표이다.

칸에 적힌 숫자는 그 칸에서 한 번에 이동해야 하는 거리(점프 거리)를 뜻한다. 이동은 오른쪽 또는 아래쪽으로만 할 수 있으며, 반드시 현재 칸에 적힌 숫자만큼 정확히 오른쪽으로 가거나 아래쪽으로 가야 한다. 숫자가 0인 칸은 더 이상 진행할 수 없는 종착점이다.

왼쪽 위 칸에서 출발하여 이 규칙을 지키면서 오른쪽 아래 칸에 도달하는 서로 다른 경로가 몇 가지인지 구하여라.

첫째 줄에 정수 N (4 ≤ N ≤ 100)이 주어진다. 이어지는 N개의 줄에는 각 줄마다 0 이상 9 이하의 숫자 N개가 공백으로 구분되어 주어진다.

왼쪽 위 칸에서 오른쪽 아래 칸까지 규칙에 맞게 이동하는 서로 다른 경로의 개수를 한 줄에 출력한다. 경로의 개수는 $2^{63}-1$보다 클 수 있지만, 100자리를 넘지는 않는다.