D. Инвертирования в турнире
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан турнир — полный ориентированный граф.

За одну операцию вы можете взять любую вершину $$$v$$$ и поменять направления всех ребер с $$$v$$$ на одном из концов (таким образом все ребра $$$u \to v$$$ меняют направление на $$$v \to u$$$ и наоборот).

Вам нужно сделать турнир сильно связным за минимальное количество таких операций.

А также, если это возможно, вам необходимо посчитать количество способов сделать турнир сильно связным за такое число операций (два способа отличаются, если для какого-то $$$i$$$, вершина выбранная на $$$i$$$-й операции одного способа, отличается от вершины выбранной на $$$i$$$-й операции другого способа). Вам нужно найти остаток от деления этой величины на $$$998\,244\,353$$$.

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

В первой строке записано одно целое число $$$n$$$ ($$$3 \leq n \leq 2000$$$): количество вершин в турнире.

Следующие $$$n$$$ строк содержат описания ребер турнира, каждая из них содержит бинарную строку длины $$$n$$$. Если $$$j$$$-й символ $$$i$$$-й строки равен '1', тогда в графе есть ребро $$$i \to j$$$.

Гарантируется, что в графе нет ребер $$$i \to i$$$ и в графе есть ровно одно ребро среди $$$i \to j$$$ и $$$j \to i$$$ для разных $$$i$$$ и $$$j$$$.

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

Если невозможно сделать турнир сильно связным за такое количество операций, выведите «-1».

Иначе, выведите два целых числа: минимальное количество операций, которое нужно, чтобы сделать турнир сильно связным и количество способов сделать турнир сильно связным за такое число операций, по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
3
010
001
100
Выходные данные
0 1
Входные данные
4
0010
1000
0100
1110
Выходные данные
-1
Входные данные
6
010000
001000
100000
111001
111100
111010
Выходные данные
2 18