강아지

어떤 마을에 $1, 2, \ldots, n$번으로 번호가 매겨진 주민 $n$명이 살고 있다. 각 주민은 개를 한 마리씩 기르며, 그 개는 건강하거나 아프다.

0일차에 한 남자가 마을에 와서 모든 주민에게 불쾌한 사실을 알려준다. 마을에 아픈 개가 적어도 한 마리 있다는 것이다.

$t$일차($t \geq 1$)에 각 주민 $i$는 $G_{i, j} = 1$인 모든 주민 $j$의 개를 검사한다. 모든 $G_{i, j}$ 값은 미리 주어지며 모든 주민이 알고 있다. 검사한 개마다 주민은 그 개가 건강한지 아픈지 알게 된다.

모든 검사가 끝난 뒤, 주민이 자기 개가 아프다고 결론 내릴 수 있으면 오후에 그 개를 쏜다. 그런 결론에 도달할 수 있는 주민이 둘 이상이면 모두 동시에 쏜다. 모든 주민은 총성을 즉시 듣는다. 그 뒤에는 다음 날이 될 때까지 아무도 개에 대해 아무것도 하지 않는다.

주민들은 위에서 설명한 방식 외에는 어떤 방법으로도 정보를 주고받지 않는다.

• 어느 날 $t$에 총성이 한 번이라도 울리면, 과정은 총살 시각 $t$로 끝난다.
• $t < 233^n$이면 과정은 $t+1$일차에 계속된다.
• 그렇지 않으면 총살 시각 $0$으로 끝난다.

개들의 건강 상태가 가능한 $2^n-1$가지 경우마다 두 값을 기록한다. 총살 시각과 총살된 개의 수다. 기록된 모든 총살 시각의 합과 총살된 개 수의 합을 구하라. 두 값 모두 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 구하라.

첫째 줄에 정수 $n$ ($1 \leq n \leq 3000$)이 주어진다.

이어지는 $n$개 줄의 $i$번째 줄에는 공백 없이 이진수 $n$자리 $G_{i, 1}, G_{i, 2}, \ldots, G_{i, n}$이 주어진다 ($G_{i, j} \in \{0, 1\}$, $G_{i, i} = 0$).

첫째 줄에 두 정수를 출력한다. 기록된 모든 총살 시각의 합과 총살된 개 수의 합을 각각 $998\,244\,353$으로 나눈 나머지다.

첫 번째 예제에서 가능한 경우는 세 가지다.

1. 1번 개는 아프고 2번 개는 건강하다. 1번 주민은 자기 개 말고는 아픈 개가 없다는 것을 알 수 있으므로 1일차에 자기 개를 쏜다.
2. 2번 개는 아프고 1번 개는 건강하다. 1일차에 1번 주민은 자기 개가 아픈지 확신하지 못하므로 아무것도 하지 않는다. 2일차에 2번 주민은 1번 주민이 1일차에 자기 개를 쏘지 않았으므로 자기 개가 아프다는 것을 안다.
3. 두 개 모두 아프다. 두 번째 경우와 비슷하게 진행된다.