Description

Every day, John bustles around to ensure the health and happiness of $n$ ($1 \leq n \leq 10$) cows.

Each cow’s position is given by a 2D coordinate, and John starts at the origin $(0, 0)$. To make the route more interesting, John decides to move only along directions parallel to the coordinate axes, that is, only north, south, east, or west. Moreover, John changes direction only upon reaching the coordinate of some cow (of course, if necessary, John may also pass through a cow’s coordinate without changing direction).

If John changes direction, he turns in place by $90^\circ$ or $180^\circ$. John’s path must visit all cows and then return to the origin.

John may pass through any cow’s coordinate without changing direction any number of times. Please compute how many routes allow John to visit all $n$ cows, such that he changes direction exactly once at each cow’s coordinate. The same geometric path traversed in the opposite direction should be counted twice.

Input Format

The first line contains an integer $n$, as described above.

The next $n$ lines each contain two space-separated integers $x$ and $y$, where line $i+1$ gives the coordinates of the $i$-th cow ($-1000 \leq x, y \leq 1000$).

Output Format

Output a single integer on one line, the number of valid routes (output 0 if there are no valid routes).

4
0 1
2 1
2 0
2 -5

2

Hint

Translated by ChatGPT 5