Ruudukko

size = int(input())
grid = []
movementgrid = []
biglist = []
for x in range(size):
    movementgrid.append([1]*size)
    grid.append(input().split(" "))
    for y in range(size):
        grid[x][y] = int(grid[x][y])
        biglist.append((grid[x][y], x, y))
biglist.sort()
shortcutsrow = {}
shortcutscol = {}
for cell, x, y in biglist:
    for y2 in range(size):
        if grid[x][y2] < cell:
            try: 
                movementgrid[x][y] += shortcutsrow[y2*1000000 + cell]
            except KeyError:
                temp = movementgrid[x][y2]
                movementgrid[x][y] += temp
                shortcutsrow[y2*1000000 + cell] = temp
                
    for x2 in range(size):
        if grid[x2][y] < cell:
            try:
                movementgrid[x][y] += shortcutscol[x2*1000000 + cell]
            except KeyError:
                temp = movementgrid[x2][y]
                movementgrid[x][y] += temp 
                shortcutscol[x2*1000000 + cell] = temp
                
total = 0
for i in movementgrid:
    total += sum(i)
print(total % 1000000007)

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