35037번 - Hello, BOJ 2026!

문제

백준고등학교에는 $N$명의 학생이 재학 중이다. 학생들은 서로 친구거나 친구가 아니며, 자기 자신과는 친구가 아니다.

백준고등학교의 교장 김기범 선생님은 학교를 대표하여 Hello, BOJ 2026!에 출전할 학생 4ドル$명을 선발하려 한다. 선발된 대표 학생들은 다음 조건을 만족해야 한다.

• 각 학생은 자신을 제외한 나머지 대표 학생 중 짝수 명과 친구여야 한다.

위 조건을 만족하도록 대표 학생 4ドル$명을 선발하는 경우의 수를 2ドル$로 나눈 나머지를 구하시오. 단, 선발된 학생들의 순서는 고려하지 않는다.

입력

첫 번째 줄에 학생의 수 $N$이 주어진다.

두 번째 줄부터 $N-1$개의 줄에 걸쳐 친구 관계에 대한 정보가 주어진다. $i+1$번째 줄은 0ドル$과 1ドル$로 구성된 길이 $N-i$의 문자열이다. $i+1$번째 줄의 $j$번째 문자는 $i$번째 학생과 $i+j$번째 학생의 친구 관계를 나타내며, 0ドル$이면 서로 친구가 아니고 1ドル$이면 서로 친구이다.

출력

대표 학생 4ドル$명을 선발하는 경우의 수를 2ドル$로 나눈 나머지를 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 4ドル\le N\le 2,円 000$

노트