Baekjoon-1890-점프

import sys
input = sys.stdin.readline

N = int(input())
maps = [[0]*N for _ in range(N)]

for n in range(N):
    maps[n] = list(map(int,input().split()))

dp = [[0]*N for _ in range(N)]
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        for k in range(i):
            if maps[k][j] == i-k:
                dp[i][j] += dp[k][j]
        for m in range(j):
            if maps[i][m] == j-m:
                dp[i][j] += dp[i][m]

print(dp[N-1][N-1])