마방진 만들기

마방진은 $N \times N$ 크기의 정사각형 칸에 $N \times N$개의 수를 한 칸에 하나씩 배열하여, 가로, 세로, 가장 긴 두 대각선 방향의 합이 모두 같게 만든 것이다. 예를 들어, 아래 그림은 $3 \times 3$ 크기의 마방진의 예시를 보여준다.

$N \times N$개의 수들이 주어질 때, 이 수들을 한 번씩 사용하여 만들 수 있는 $N \times N$ 크기의 서로 다른 마방진은 모두 몇 개인지 구하는 프로그램을 작성하시오.

$N = 3$이고 $N \times N = 9$개의 수가 $9, 8, 7, 6, 5, 4, 3, 2, 1$로 주어진 예를 생각해보자. 아래와 같이 총 $4 \times 2 = 8$가지 마방진을 만들 수 있음을 알 수 있다.

• 이 문제에서 처음 주어진 마방진은 주어진 입력으로 만들 수 있는 마방진 중 하나이다.
• 처음 주어진 마방진을 시계 방향으로 $90$도 회전하면 다음과 같이 또다른 마방진을 만들 수 있다.

• 시계 방향으로 $180$도, $270$도 회전해도 또다른 마방진을 만들 수 있다.
• 마지막으로, 위에서 만든 마방진을 좌우로 뒤집어도 새로운 마방진을 만들 수 있다. 예를 들어 아래의 마방진은 처음 마방진을 좌우로 뒤집은 것이다.

입력 형식

첫 줄에 마방진의 크기를 나타내는 정수 $N$이 주어진다. $(2 \le N \le 4)$

그다음 줄에 마방진에 사용할 $N \times N$개의 정수가 공백으로 구분되어 주어진다. 이 수들은 모두 $0$ 이상 $100$ 이하이다.

출력 형식

첫 줄에 만들 수 있는 서로 다른 마방진의 수를 출력한다.

예제 1

3
9 8 7 6 5 4 3 2 1

8

예제 2

2
1 0 1 0

0

예제 3

4
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4

256

예제 4

3
0 0 0 0 0 0 0 0 0

1

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설