409038: GYM103426 B Permutations

Recently Manya learned that a permutation is a sequence of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$2,3,1,5,4$$$ is a permutation, but $$$1,2,2$$$ is not a permutation ($$$2$$$ appears twice) and $$$1,3,4$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the sequence).

Manya started to write down random permutations, one under another. She wrote down $$$n-1$$$ permutations and realized that a column in the resulting table of integers can also turn out to be a permutation when Manya writes down the $$$n$$$th permutation. Every column will consist of $$$n$$$ integers from $$$1$$$ to $$$n$$$, however, not every column will be a valid permutation. Then Many decided to add the $$$n$$$th permutation in a way to maximize the number of columns-permutations.

Your task is to find out the maximum number of columns that could be permutations after adding the $$$n$$$th permutation; and how many permutations will result in the highest number of columns-permutations.

The first line contains a single integer $$$n$$$ — the permutation length ($$$2 \le n \le 1000$$$).

Each of the next $$$n-1$$$ lines contains a permutation of length $$$n$$$ — $$$n$$$ integers from $$$1$$$ to $$$n$$$.

Output two integers — the maximum number of column-permutations that can be achieved after adding a permutation; and the number of permutations that can be added to achieve the highest number of columns-permutations modulo $$$10^9 + 7$$$.

4
1 2 3 4
4 1 2 3
3 2 4 1

2 4

4
1 2 3 4
1 2 4 3
2 1 4 3

0 24

In the first example, the first column needs $$$2$$$ to be a permutation as well as the fourth column, the third column needs $$$1$$$. Manya can add permutations:

$$$2,3,1,4$$$;

$$$2,4,1,3$$$;

$$$3,4,1,2$$$;

$$$4,3,1,2$$$;

to get two columns-permutations. It is not possible to get a result with three columns-permutations as the $$$n$$$th permutation can not contain two $$$2$$$.

In the second example, none of the columns will be a valid permutation, no matter what permutation Manya adds. That means that the maximum number of columns-permutations is $$$0$$$ and can be achieved by adding any of the $$$24$$$ permutations.