2122번 - 여섯이서 놀기

문제

사람들이 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)이 주어진다. 그리고 서로 아는지에 관한 관계가 인접행렬로 주어진다. A가 B를 알면 물론 B도 A를 안다.

출력

첫 줄에 가능한 모든 경우의 수를 출력한다. 단, 답이 클 수 있으므로 9901로 나눈 나머지를 출력한다.

제한

힌트

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