Ruudukko

n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
 
minmap = [[[]*n for _ in range(n)] for _ in range(n)]
nums = [[0 for _ in range(n)] for _ in range(n)]
 
def generateminmap(x, y):
    global g, n, minmap
 
    for j in range(n):
        if g[x][j] < g[x][y] and x+j != x+y:
            minmap[x][y].append([x, j])
 
    for i in range(n):
        if g[i][y] < g[x][y] and i+y != x+y:
            minmap[x][y].append([i, y])
    
for i in range(n):
    for j in range(n):
        generateminmap(i, j)
 
def explorenode(cur, node, depth):
    global minmap, nums
 
    for i in node:
        if node != []:
            nums[cur[0]][cur[1]] += 1
            depth = explorenode(cur, minmap[i[0]][i[1]], depth)
ans = 0
for i in range(n):
    for j in range(n):
        explorenode([i,j], minmap[i][j], 0)
        ans += nums[i][j]
 
 
j = pow(10, 9)+7
ans += n*n
ans = ans%j
print(ans)
 
"""
grid:
3
2 1 3
1 1 1
9 2 7
 
smallest numbers in rows+columns:
2 0 3
0 0 0
4 2 3
 
"""

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED