색깔 완전 매칭의 개수

그래프 $G$가 주어진다. $G$에는 검은색 정점 $n$개와 흰색 정점 $n$개가 있으며, 모든 간선은 검은색 정점과 흰색 정점을 잇는다. 따라서 그래프는 이분 그래프이다.

$G$의 각 간선은 파란색 또는 빨간색이다. 같은 색의 간선 두 개가 같은 두 정점을 잇는 경우는 없다. 즉, 같은 색의 중복 간선은 없다.

$0$부터 $n$까지의 모든 $k$에 대해, 빨간색 간선을 정확히 $k$개, 파란색 간선을 정확히 $n-k$개 포함하는 완전 매칭의 개수를 구하라. 완전 매칭은 어떤 두 간선도 끝점을 공유하지 않는 $n$개의 간선 집합이다. 개수가 매우 클 수 있으므로 각 개수를 2로 나눈 나머지로만 출력한다.

첫 줄에 음이 아닌 정수 $n$ ($1 \le n \le 300$)이 주어진다.

이어지는 $n$개의 줄에는 공백 없이 $n$개의 문자가 주어지며, 빨간색 간선의 인접 행렬을 나타낸다. $i$번째 줄의 $j$번째 문자가 1이면 $i$번째 검은색 정점과 $j$번째 흰색 정점을 잇는 빨간색 간선이 있고, 0이면 없다.

다음 $n$개의 줄은 같은 형식으로 파란색 간선의 인접 행렬을 나타낸다.

$n + 1$개의 줄을 출력한다. $k$번째 줄 ($k = 0, 1, \ldots, n$)에는 빨간색 간선을 정확히 $k$개 포함하는 완전 매칭의 개수를 2로 나눈 나머지를 출력한다.

예시에서 완전 매칭은 세 가지이다.

1. 빨간색 $(1, 1)$, 파란색 $(2, 2)$
2. 빨간색 $(1, 2)$, 파란색 $(2, 1)$
3. 빨간색 $(1, 2)$, 빨간색 $(2, 1)$