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 = [[{1: 0}, 1, 1] for _ in range(n)]
line_values_col = [[{1: 0}, 1, 1] for _ in range(n)]
"line_values_col[x] is a list of a dict and two ints, the first int equals the greatest key value in the dict, the second is the highest known number that has the same value as the greatest key"


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"""
    "naive"
    # if v in line_values_row[y][0].keys():
    #     return line_values_row[y][0][v]
    # s = 0
    # for x in range(n):
    #     if grid[y][x] < v:
    #         s += route_grid[y][x]
    # line_values_row[y][0][v] = s
    # return s
    if v == line_values_row[y][2]:
        return line_values_row[y][0][line_values_row[y][1]]
    if (line_values_row[y][2] == v - 1) and (v - 1 not in [grid[y][x] for x in range(n)]):
        line_values_row[y][2] = v
        return line_values_row[y][0][line_values_row[y][1]]
    s = 0
    for x in range(n):
        if grid[y][x] < v:
            s += route_grid[y][x]
    line_values_row[y][0][v] = s
    line_values_row[y][1] = v
    line_values_row[y][2] = v

    return s


def get_line_values_col(x: int, v: int):
    "naive"

    if v == line_values_col[x][2]:
        return line_values_col[x][0][line_values_col[x][1]]
    if (line_values_col[x][2] == v - 1) and (v - 1 not in [grid[y][x] for y in range(n)]):
        line_values_col[x][2] = v
        return line_values_col[x][0][line_values_col[x][1]]
    s = 0
    for y in range(n):
        if grid[y][x] < v:
            s += route_grid[y][x]
    line_values_col[x][0][v] = s
    line_values_col[x][1] = v
    line_values_col[x][2] = v

    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):
    ready = True
    for y in range(n):
        if None not in route_grid[y]:
            continue
        ready = False
        x = -1
        while True:
            try:
                x = grid[y].index(a, x + 1)
                calculate_routes(y, x)

            except ValueError:
                break
    if ready:
        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: ACCEPTED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED