B. Permutations
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Маня узнала, что перестановка — это последовательность из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$2,3,1,5,4$$$ — перестановка, но $$$1,2,2$$$ не перестановка ($$$2$$$ встречается дважды) и $$$1,3,4$$$ тоже не перестановка ($$$n=3$$$, но в последовательности встречается $$$4$$$).

Маня начала выписывать случайные перестановки одну под другой. Когда она выписала $$$n-1$$$ перестановку, Маня заметила, что столбцы в получающейся таблице чисел тоже могут оказаться перестановками из $$$n$$$ чисел, когда она выпишет $$$n$$$-ю перестановку. В каждом столбце будет по $$$n$$$ чисел от $$$1$$$ до $$$n$$$, но не все столбцы будут являться корректными перестановками. Тогда Маня решила, что хочет дописать $$$n$$$-ю перестановку так, чтобы количество столбцов-перестановок было как можно больше.

Ваша задача — узнать, какое наибольшее число столбцов может оказаться перестановками после добавления $$$n$$$-й перестановки; и сколько существует перестановок, выписав которые, можно получить наибольшее число столбцов-перестановок.

Входные данные

Первая строка содержит число $$$n$$$ — длину перестановок ($$$2 \le n \le 1000$$$).

Каждая из следующих $$$n-1$$$ строк содержит перестановку длины $$$n$$$ — $$$n$$$ чисел от $$$1$$$ до $$$n$$$.

Выходные данные

Выведите два числа через пробел — наибольшее число столбцов, которые могут оказаться перестановками после добавления перестановки, и число перестановок, которые можно добавить для достижения наибольшего числа столбцов-перестановок, по модулю $$$10^9 + 7$$$.

Система оценки
ПодзадачаБаллыОграничения
120$$$n \le 7$$$
245$$$n \le 300$$$
335$$$n \le 1000$$$
Примеры
Входные данные
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
Примечание

В первом примере в первый и четвертый столбцы нужно дописать $$$2$$$, чтобы они стали перестановками. В третий столбец можно дописать $$$1$$$. Тогда, если Маня добавит одну из перестановок:

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

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

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

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

получится два столбца-перестановки. Получить три столбца-перестановки в этом примере не получится, так как в дописанной перестановке не может быть два числа $$$2$$$.

Во втором примере ни один из столбцов не будет являться перестановкой, какую бы перестановку Маня не дописала. Значит, наибольшее число столбцов-перестановок равно $$$0$$$, и его можно получить добавив любую из $$$24$$$ перестановок.