Dogs

In a village, there are $n$ villagers labeled with $1, 2, \ldots, n$. Each villager keeps a dog, and the dog is either healthy or sick.

On day $0$, a man comes to the village and tells all the villagers an unpleasant truth: there is at least one sick dog in the village.

On day $t$ ($t \geq 1$), each villager $i$ inspects the dog of every villager $j$ such that $G_{i, j} = 1$. All values $G_{i, j}$ are given in advance and known to all the villagers. For each dog inspected, the villager learns whether it is healthy or sick.

After all the inspections, if a villager can conclude that his own dog is sick, he shoots it in the afternoon. If more than one villager can reach such a conclusion, they all shoot simultaneously. All villagers immediately hear the shots. After that, nobody does anything about dogs until the next day.

The villagers do not exchange information in any way except what is described above.

• If any shooting occurs on day $t$, the process ends with shoot time $t$.
• If $t < 233^n$, the process continues on day $t+1$.
• Otherwise, the process ends with shoot time $0$.

For each of the $2^n-1$ possible health states of the dogs, we record two values: the shoot time and the number of dogs shot. Find two sums: the sum of all recorded shoot times and the sum of the numbers of dogs shot. Since both may be very large, output them modulo $998\,244\,353$.

The first line contains an integer $n$ ($1 \leq n \leq 3000$).

The $i$-th of the following $n$ lines contains $n$ binary digits without spaces: $G_{i, 1}, G_{i, 2}, \ldots, G_{i, n}$ ($G_{i, j} \in \{0, 1\}$, $G_{i, i} = 0$).

On the first line, print two integers: the sum of all recorded shoot times and the sum of the numbers of dogs shot, both modulo $998\,244\,353$.

For the first sample, there are three possible configurations:

1. Dog 1 is sick and dog 2 is healthy. Villager 1 finds no other sick dog, so he shoots his own dog on day 1.
2. Dog 2 is sick and dog 1 is healthy. On day 1, villager 1 is not sure about his own dog, so he does nothing. On day 2, villager 2 knows his dog must be sick, or villager 1 would have shot his own dog on day 1.
3. Both dogs are sick. This case is similar to the second one.