Ruudukko

# completes tests 1 and 2, but not 3
import random
import time
import sys
from typing import Generator, TypeVar


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


DIVISOR = 10**9 + 7

_V = TypeVar("_V")

test_N = 1000

test_expected_results = {
    100: 773224951,
    200: 452330452,
    300: 37161558,
    400: 250332178,
    1000: 298053617
}


def test():
    n = test_N

    def text_gen():
        yield str(n)
        random.seed(1001)
        for i in range(n):
            yield " ".join((str(random.randint(1, n * n)) for _ in range(n)))

    return text_gen().__next__


input = test()


class Node:
    "Binary Search Tree node"

    def __init__(self, parent: "Node|None", left: "Node|None", right: "Node|None", key: "int|float"):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
        self.values = []
        self.marker = 0
        pass

    def Get(self) -> "list":
        return self.values
        ...

    def Add(self, value):
        self.values.append(value)

    def next(self):
        if self.marker == 0:
            self.marker += 1
            if self.left:
                return self.left
        if self.marker == 1:
            self.marker += 1
            if self.right:
                return self.right
        self.marker = 0
        return self.parent


class BST:
    def __init__(self, middle: float):
        self.root = Node(None, None, None, middle)

    def Insert(self, key: "int | float", value: "_V"):

        node, pos = self.search(key)
        if pos == 1:
            node.left = Node(node, None, None, key)
            node.left.Add(value)
        elif pos == 2:
            node.right = Node(node, None, None, key)
            node.right.Add(value)
        else:
            node.Add(value)

    # def Get(self, key: "int | float") -> "Node":
    #     ...

    def Iter(self) -> "Generator[Node,None,None]":
        node = self.root
        while 1:
            new = node.next()
            if new is None:
                break
            if node.marker == 0:
                # new is parent
                if new.marker == 1:
                    # node is left
                    yield new
            elif new.left is None:
                yield new
            # elif node.marker == 1:
            #     # new is right child
            node = new

    def Iter_Values(self):
        # for node in self.Iter():
        #     for x, y in node.Get():
        #         yield node.key, x, y
        return ((node.key, v) for node in self.Iter() for v in node.Get())

    def search(self, key: "int|float") -> "tuple[Node, int]":
        """returns a node and a number. 
        0 means the node has the wanted value, 
        1 means the value doesn't exist but would be the node's left branch if inserted,
        2 means the same as 1 but for the right branch."""
        # no recursion
        current = self.root
        while 1:
            if key < current.key:
                if current.left:
                    current = current.left
                else:
                    return current, 1
            elif key > current.key:
                if current.right:
                    current = current.right
                else:
                    return current, 2
            else:
                return current, 0


def main():

    timer_0 = time.perf_counter()
    n, = I()
    grid = [list(I()) for _ in range(n)]
    total = 0

    timer_1 = time.perf_counter()
    print("timer 1:", timer_1 - timer_0, file=sys.stderr)
    line_row = [0] * n
    line_row_last = [1] * n
    line_col = [0] * n
    line_col_last = [1] * n
    line_row_added = [0] * n
    line_col_added = [0] * n

    # exists_row = [set(g) for g in grid]
    # exists_all = set().union(*exists_row)
    # print("exists_all size:", len(exists_all))
    # values_coords = BST(n * n // 2)
    sett = set()

    for y in range(n):
        for x in range(n):
            # values_coords.Insert(grid[y][x], (x, y))
            sett.add((grid[y][x], x, y))

    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 v == line_row_last[y]:  # false <==> first time with this y and v
            return line_row[y]

        line_row_last[y] = v

        s = line_row[y] + line_row_added[y]
        line_row_added[y] = 0
        line_row[y] = s

        return s

    def get_line_values_col(x: int, v: int):
        if v == line_col_last[x]:
            return line_col[x]

        line_col_last[x] = v

        s = line_col[x] + line_col_added[x]
        line_col_added[x] = 0
        line_col[x] = s

        return s

    def calculate_routes(y: int, x: int, number: int):
        if number == 1:
            value = 1
        else:
            value = (get_line_values_col(x, number) + get_line_values_row(y, number) + 1) % DIVISOR
        # nonlocal total
        # total += value
        line_row_added[y] += value
        line_col_added[x] += value
        return value

    timer_2 = time.perf_counter()
    print("timer 2:", timer_2 - timer_1, file=sys.stderr)
    sor = sorted(sett)
    timer_3 = time.perf_counter()
    print("timer 3:", timer_3 - timer_2, file=sys.stderr)

    total = sum(calculate_routes(y, x, k)for k, x, y in sor)
    timer_4 = time.perf_counter()
    print("timer 4:", timer_4 - timer_3, file=sys.stderr)

    return total % DIVISOR


def old_iteration(n, grid, exists_row, exists_all, calculate_routes):
    for a in range(1, n * n + 1):
        if a not in exists_all:
            continue
        for y in range(n):
            if a not in exists_row[y]:
                continue
            x = -1
            try:
                while True:
                    x = grid[y].index(a, x + 1)
                    calculate_routes(y, x, a)
            except ValueError:
                pass


timer_start = time.perf_counter()
w = main()
print(w)
# 100: 773224951
# 200: 452330452
print("time:", time.perf_counter() - timer_start,
      ("\ncorrect" if w == test_expected_results[test_N] else "\ndifferent") if test_N in test_expected_results.keys() else "no data", file=sys.stderr)

Test 1

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

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