여섯 명이서 놀기

사람이 N명 있다. 이 중 서로 다른 여섯 명을 골라 원형으로 서서 놀이를 하려고 한다.

서로 이웃한 사람끼리는 손을 잡아야 하므로, 원 안의 각 사람은 양옆에 선 두 사람을 모두 알고 있어야 한다. 같은 여섯 명을 골랐더라도 원형 순서가 달라지면 다른 배치가 될 수 있다. 단, 회전해서 같아지는 배치는 같은 것으로 보며, 같은 순서를 반대 방향으로 읽은 배치도 같은 것으로 본다. 예를 들어 (1-2-3-4-5-6-1)과 (1-6-5-4-3-2-1)은 같은 한 가지이고, (1-2-3-4-5-6-1)과 (1-2-4-3-5-6-1)은 다른 경우이다.

만들 수 있는 원형 배치의 수를 모두 구하자.

첫 줄에 후보자의 수 N(6 <= N <= 150)이 주어진다.

다음 N개의 줄에는 서로 아는 관계가 인접 행렬로 주어진다. A가 B를 알면 B도 A를 안다.

가능한 모든 원형 배치의 수를 9901로 나눈 나머지를 출력한다.

N = 6인 완전 그래프의 답은 60이고, N = 7인 완전 그래프의 답은 420이다.