준규와 사과

준규는 가로 5m, 세로 5m 크기의 땅을 가지고 있다. 이 땅을 가로 1m, 세로 1m 크기의 정사각형 칸 25개로 나눈다. 가장 왼쪽 위 칸이 (1, 1)이고 가장 오른쪽 아래 칸이 (5, 5)이며, 칸 (i, j)에서 i는 위에서부터 센 행 번호, j는 왼쪽에서부터 센 열 번호이다.

(1,1) (1,2) (1,3) (1,4) (1,5)
(2,1) (2,2) (2,3) (2,4) (2,5)
(3,1) (3,2) (3,3) (3,4) (3,5)
(4,1) (4,2) (4,3) (4,4) (4,5)
(5,1) (5,2) (5,3) (5,4) (5,5)

25개 칸 중 $K$개의 칸에는 거대한 돌이 있어 사과 나무가 없고, 나머지 칸에는 사과 나무가 하나씩 심어져 있다. 칸 (1, 1)과 (5, 5)에는 항상 사과 나무가 있다.

준규와 친구 해빈이가 함께 모든 사과를 수확한다. 준규는 (1, 1)에서, 해빈이는 (5, 5)에서 출발한다. 두 사람은 같은 규칙에 따라 같은 속도로 움직인다.

• 한 칸에 있는 사과 나무의 사과를 모두 수확하는 데 30분이 걸린다.
• 현재 칸의 수확을 마치면 상하좌우로 인접하면서 사과 나무가 있는 칸으로 이동하며, 이동에도 30분이 걸린다.
• 사과 나무가 없는 칸이나 이미 수확이 끝난 칸으로는 이동할 수 없다.
• 마지막 칸을 제외하면 두 사람은 같은 칸에 동시에 있을 수 없다.

두 사람은 땅에 있는 모든 사과를 빠짐없이 수확하고, 마지막에는 같은 칸에서 만난다. 이렇게 사과를 수확하는 서로 다른 방법의 수를 구하시오.

첫째 줄에 사과 나무가 없는 칸의 개수 $K$가 주어진다. $K$는 짝수이고 $0 \le K \le 22$이다.

다음 $K$개의 줄에는 사과 나무가 없는 칸의 위치가 한 줄에 하나씩, 행 번호 $i$와 열 번호 $j$가 공백으로 구분되어 주어진다 ($1 \le i, j \le 5$). 칸 (1, 1)과 (5, 5)에는 항상 사과 나무가 있으므로 이 목록에는 나타나지 않는다.

규칙을 지키며 모든 사과를 수확하는 서로 다른 방법의 수를 한 줄에 출력한다. 가능한 방법이 없으면 0을 출력한다.

사과 나무가 없는 칸이 (3, 1), (3, 2), (3, 3), (3, 4)인 경우를 그림으로 나타내면 다음과 같다. 점(.)은 사과 나무가 있는 칸, x는 없는 칸, j는 준규의 시작 위치, h는 해빈이의 시작 위치이다.

j  .  .  .  .

.  .  .  .  .

x  x  x  x  .

.  .  .  .  .

.  .  .  .  h

이 경우 규칙을 지키며 모든 사과를 수확하는 방법은 다음 한 가지뿐이다.

j  j--j  j--j
|  |  |  |  |
j--j  j--j  j
            |
x  x  x  x j/h
            |
h--h--h--h--h
|
h--h--h--h--h