Недавно Маня узнала, что перестановка — это последовательность из $$$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$$$.
| Подзадача | Баллы | Ограничения |
| 1 | 20 | $$$n \le 7$$$ |
| 2 | 45 | $$$n \le 300$$$ |
| 3 | 35 | $$$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$$$ перестановок.
