Ruudukko

def I():
    return map(int, input().split())


n, = I()
grid = [list(I()) for _ in range(n)]
route_grid = [[None] * n for _ in range(n)]
"route_grid[y][x] is how many routes can start from the tile. None if it hasn't been calculated yet"
line_values_row = [[0, {}] for _ in range(n)]
line_values_col = [[0, {}] for _ in range(n)]
"line_values_col[x] is a list of an int and a dict, the int equals the largest key value in the dict"


def get_line_values_row(y: int, v: int):
    """tells how many routes can start from a tile of value v and first go along row y \n
    sum of the route values of tiles less than v on row y"""
    # if line_values_row[y][0]:
    #     pass
    "naive"
    s = 0
    for x in range(n):
        if grid[y][x] < v:
            s += route_grid[y][x]
    return s


def get_line_values_col(x: int, v: int):
    "naive"
    s = 0
    for y in range(n):
        if grid[y][x] < v:
            s += route_grid[y][x]
    return s


def calculate_routes(y: int, x: int):

    number = grid[y][x]
    if number == 1:
        route_grid[y][x] = 1
        return
    else:
        route_grid[y][x] = get_line_values_col(x, number) + get_line_values_row(y, number) + 1


for a in range(1, n * n + 1):
    for y in range(n):
        if None not in route_grid[y]:
            continue
        x = -1
        while True:
            try:
                x = grid[y].index(a, x + 1)
                calculate_routes(y, x)

            except ValueError:
                break


divisor = 10**9 + 7


def summod(x):
    return sum(y % divisor for y in x) % divisor


w = summod(map(summod, route_grid))
print(w)

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: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED