Junkyu and the Apples

Junkyu owns a plot of land that is 5m wide and 5m tall. He divides it into 25 square cells, each 1m by 1m. The top-left cell is (1, 1) and the bottom-right cell is (5, 5); in a cell (i, j), i is the row number counted from the top and j is the column number counted from the left.

(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)

Exactly $K$ of the 25 cells contain a huge rock and have no apple tree; every other cell has exactly one apple tree. Cells (1, 1) and (5, 5) always contain an apple tree.

Junkyu and his friend Haebin harvest all the apples together. Junkyu starts at (1, 1) and Haebin starts at (5, 5). Both follow the same rules and move at the same speed.

• Harvesting every apple on the tree in one cell takes 30 minutes.
• After finishing the current cell, a harvester moves to an orthogonally adjacent cell that still has an apple tree; each move also takes 30 minutes.
• A harvester may never move onto a cell that has no apple tree or whose tree has already been harvested.
• Except for the very last cell, the two harvesters can never be on the same cell at the same time.

The two harvest every apple on the land and meet on the same cell at the end. Count the number of distinct ways they can do this.

The first line contains $K$, the number of cells without an apple tree. $K$ is even and $0 \le K \le 22$.

Each of the next $K$ lines contains the location of one such cell as a row number $i$ and a column number $j$ separated by a space ($1 \le i, j \le 5$). Cells (1, 1) and (5, 5) always contain an apple tree, so they never appear in this list.

Print, on a single line, the number of distinct ways to harvest every apple while following the rules. If there is no valid way, print 0.

The figure below illustrates the case where the cells without an apple tree are (3, 1), (3, 2), (3, 3), and (3, 4). A dot (.) is a cell with an apple tree, x is a cell without one, j is Junkyu's starting cell, and h is Haebin's starting cell.

j  .  .  .  .

.  .  .  .  .

x  x  x  x  .

.  .  .  .  .

.  .  .  .  h

In this case there is exactly one way to harvest all the apples while following the rules:

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