페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4028

제3회 디미고 프로그래밍 챌린지 오픈 콘테스트

별자리 1초 1024MB

문제

천문학자 압둘은 매일 밤 광덕산에 올라 정육면체 모양의 별자리 모나드를 관측한다. 압둘이 관측을 시작하기 전날 밤, 모나드는 아래 그림과 같은 형태를 띠고 있었다.

그러나 모나드는 매우 활발한 별자리여서, 관측 중에도 끊임없이 회전되거나 반전되어 별들의 절대적인 위치를 알아보기 어렵다. 이러한 이유로 압둘은 별들의 인접 관계만을 기록하였다.

매일 해가 뜨면, 서로 인접한 두 별이 위치를 맞바꾸는 현상이 한 번 발생한다. 압둘은 매일 매일 관측 결과들을 정리해왔지만, 사소한 실수로 마지막 날을 제외한 나머지 자료를 모두 잃어버리고 말았다.

불쌍한 압둘을 위해 가능한 기록의 가짓수라도 구해주자.


입력

첫 번째 줄에 압둘이 관측한 날의 수 1<=N<=1,000,000,000이 주어진다.

둘째 줄부터 6개의 줄에 걸쳐 마지막 날의 별들의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i번 별과 j번 별이 인접해 있다는 뜻이고, 0인 경우는 인접해 있지 않다는 뜻이다.

단, 모나드의 형태를 가지지 않는 별자리의 인접 행렬은 주어지지 않는다.


출력

첫 번째 줄에 가능한 별자리 기록의 가짓수를 1\,000\,000\,007로 나눈 나머지를 출력한다.


예제 #1

999999993
0 1 1 0 1 1
1 0 1 1 0 1
1 1 0 1 1 0
0 1 1 0 1 1
1 0 1 1 0 1
1 1 0 1 1 0
599373256

예제 #2

190706854
0 1 1 0 1 1
1 0 1 1 0 1
1 1 0 1 1 0
0 1 1 0 1 1
1 0 1 1 0 1
1 1 0 1 1 0
166154308

예제 #3

1
0 1 1 1 1 0
1 0 0 1 1 1
1 0 0 1 1 1
1 1 1 0 0 1
1 1 1 0 0 1
0 1 1 1 1 0
2

예제 #4

2
0 1 1 0 1 1
1 0 0 1 1 1
1 0 0 1 1 1
0 1 1 0 1 1
1 1 1 1 0 0
1 1 1 1 0 0
12
로그인해야 코드를 작성할 수 있어요.