Ruudukko

paths = {}
n = int(input())
ruudukko = []
smallestNum = n * n + 1
q = []
notUsed = []
values = []
for i in range(n):
    row = input().split()
    ruudukko.append(row)
    for j in range(n):
        notUsed.append((i, j))
        values.append(ruudukko[i][j])
        paths[(i, j)] = 1
        num = int(row[j])
        if num < smallestNum:
            smallestNum = num
            q = [(i, j)]
        elif num == smallestNum:
            q.append((i, j))
 
notUsed = [val for (_, val) in sorted(zip(values, notUsed), key=lambda x: x[0])]
 
def getPoints(startPoint):
    nextPoints = []
    i = startPoint[0]
    j = startPoint[1]
    i2 = 0
    j2 = 0
    while i2 < n:
        if ruudukko[i2][j] > ruudukko[i][j] and i2 != i:
            nextPoints.append((i2, j))
        i2 += 1
    while j2 < n:
        if ruudukko[i][j2] > ruudukko[i][j] and j2 != j:
            nextPoints.append((i, j2))
        j2 += 1
    return nextPoints
 
def getStartPoint():
    if len(q): return q.pop(0)
    elif len(notUsed): return notUsed.pop(0)
 
while True:
    startPoint = getStartPoint()
    if not startPoint:
        break
    nextPoints = getPoints(startPoint)
    if startPoint in notUsed:
        notUsed.remove(startPoint)
    for nextPoint in nextPoints:
        if nextPoint in notUsed:
            paths[nextPoint] += paths[startPoint]
            q.append(nextPoint)
 
ans = sum(paths.values()) % 1000000007
print(ans)

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3

Verdict: WRONG ANSWER

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