정육면체

바이트맨(Byteman)은 바이트크립트(ByteCrypt)라는 새로운 준(準)디지털 서명 시스템을 고안했다. 이 시스템에서 각 사용자는 문서에 서명할 때 쓰는 개인 열쇠를 하나 받는데, 이 열쇠는 한 변의 길이가 $n$인 속이 빈 정육면체 모양이다. 모든 정육면체의 각 면은 $n \times n$개의 칸으로 나뉘며, 각 칸에는 칩이 정확히 하나(암호화 칩 또는 범용 칩) 놓이거나 비어 있다.

모든 암호화 칩은 서로 완전히 같고, 마찬가지로 임의의 두 범용 칩도 서로 같다. 암호화 칩이 만드는 무늬는 모든 정육면체의 모든 면에서 동일하다. 즉 각 면을 적절히 회전하면 모든 정육면체의 모든 면에서 암호화 칩 무늬가 정확히 일치하도록 만들 수 있다. 두 면을 구별하는 유일한 차이는 나머지 칸 중 어디에 범용 칩이 놓였는지뿐이다. 또한 모든 칩은 항상 각 면의 한쪽 표면, 곧 정육면체 안쪽을 향하는 표면에만 놓인다.

바이트해커(Bytehacker)는 바이트크립트를 깨뜨리려 하며, 이미 정육면체 열쇠를 위조하는 방법을 알고 있다. 그는 시스템의 어떤 사용자로든 위장하기 위해 열쇠가 몇 개 필요한지 알고 싶다. 더 정확히 말하면, 가능한 모든 사용자 열쇠(각 면의 범용 칩 배치와, 면들을 정육면체로 조립한 방식으로 정해진다)에 대해 바이트해커는 다음 성질을 가진 열쇠를 하나 갖고 싶어 한다: 그 열쇠를 여섯 개의 면으로 분해한 뒤 면들을 자유롭게 재배치하고 회전하여 새 정육면체로 다시 조립하면, 그 결과가 해당 사용자 열쇠와 동일해진다. 두 열쇠는 한쪽을 회전하여 다른 쪽과 일치시킬 수 있으면 동일하다고 한다.

다음을 수행하는 프로그램을 작성하라.

• 정육면체 열쇠의 한 변의 길이와 한 면의 암호화 칩 무늬를 입력받는다.
• 바이트해커에게 필요한 열쇠의 최소 개수를 구한다.
• 그 값을 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 양의 정수 $n$이 하나 주어진다 ($n \le 1000$). 이어지는 $n$개의 줄에는 각각 $n$개의 정수 $a_{ij} \in \{0, 1\}$가 공백 하나로 구분되어 주어진다. $a_{ij} = 1$은 모든 면의 $i$번째 행, $j$번째 열 칸에 암호화 칩이 있음을 뜻한다. $a_{ij} = 0$은 그 칸에 암호화 칩이 없어 비어 있거나 범용 칩이 놓일 수 있음을 뜻한다.

바이트해커에게 필요한 열쇠의 개수를 $10^9 + 7$로 나눈 나머지를 정수 하나로 출력한다.