Connect the Cows

Every day Farmer John walks around his farm to check on his $N$ cows ($1 \le N \le 10$).

Each cow's location is a point in the 2D plane, and Farmer John starts at the origin $(0, 0)$. He walks only in directions parallel to the coordinate axes — north, south, east, or west. He may change his direction of travel only at the location of a cow; he may also pass straight through a cow's location without turning as many times as he likes. When he does turn, the turn is either $90$ degrees or $180$ degrees. His route must return him to the origin after visiting all of his cows.

Count the number of different routes Farmer John can take so that he turns exactly once at the location of each cow. A route and the same route walked in reverse count as two different routes.

• The first line contains the integer $N$.
• Each of the next $N$ lines contains two space-separated integers, the $x$ and $y$ coordinates of a cow (each coordinate is in the range $-1000 \ldots 1000$).

• Print a single line containing the number of different routes Farmer John can take. This may be $0$ if no valid route exists.

In the sample there are $4$ cows, at $(0,1)$, $(2,1)$, $(2,0)$, and $(2,-5)$. There are two valid routes: Farmer John may turn at the cows in the order $(0,1) \to (2,1) \to (2,-5) \to (2,0)$, or in the exact reverse order. Because a route and its reverse are counted separately, the answer is $2$.