Counting Axis‐Aligned Farm Paths

Every day, John needs to check on the health and happiness of n cows on his farm. The positions of the cows are given as 2D coordinates. John starts at the origin \((0,0)\) and can only move in directions parallel to the coordinate axes (i.e. east, north, west, south).

John chooses his path so that he only changes direction when he arrives at a cow’s coordinate and at that moment he must change direction exactly once. At a cow’s position, he may turn either \(90^\circ\) (left or right) or \(180^\circ\) (i.e. reverse his current direction). Of course, John may pass through any cow’s coordinate without turning if he wishes. After having performed a turn exactly once at each of the \(n\) cow positions (in some order, not necessarily the order in which they appear on his initial journey), his path must eventually return to the origin \((0,0)\).

Note that if the same path is traversed in different ways (i.e. the same geometric route but with different directions when passing the same point), they are counted as different. Also, the initial direction is chosen arbitrarily from the four cardinal directions if it leads to a valid path.

Input constraints: \(1 \le n \le 10\).

Movement details:

• The path is divided into segments. The initial segment starts at \((0,0)\) and moves straight (without turning) along one of the four axes directions until it reaches the first cow where a turn is performed.
• After turning at a cow, the next segment is again a straight line in the new direction until the next cow (at which point a turn must be made), and so on.
• When all cows have been visited (i.e. a turn has been performed exactly once at each cow’s coordinate), John must continue in a straight line (with no further turns) until he returns to \((0,0)\). In order for \((0,0)\) to lie on the ray defined by his current position and direction, certain alignment conditions must be met.

What to compute: Count the number of distinct valid paths that satisfy the above conditions. Two paths that are identical in geometry but differ by the direction from which they are traversed are counted separately.

Movement conditions:

• If moving east, a cow is reachable if its y-coordinate equals the current y and its x-coordinate is greater than the current x.
• If moving north, a cow is reachable if its x-coordinate equals the current x and its y-coordinate is greater than the current y.
• If moving west, a cow is reachable if its y-coordinate equals the current y and its x-coordinate is less than the current x.
• If moving south, a cow is reachable if its x-coordinate equals the current x and its y-coordinate is less than the current y.

At each cow (when chosen for turning), John has three turning options: turn \(90^\circ\) left, turn \(90^\circ\) right, or turn \(180^\circ\).

Returning to the origin:

Once all cows have been visited, John must travel in a straight line (with no further turns) from his current position to \((0,0)\). That is possible only if \((0,0)\) lies on the ray of his current direction from his current position. For example:

• If his current direction is east then his current y-coordinate must be \(0\) and \(0\) (the x-coordinate of the origin) must be greater than his current x.
• If his current direction is north then his current x-coordinate must be \(0\) and \(0\) (the y-coordinate of the origin) must be greater than his current y.
• If his current direction is west then his current y-coordinate must be \(0\) and \(0\) must be less than his current x.
• If his current direction is south then his current x-coordinate must be \(0\) and \(0\) must be less than his current y.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10\)) – the number of cows. The next \(n\) lines each contain two integers representing the coordinates of a cow.

It is guaranteed that the coordinates are such that a path (if exists) follows the rules described.

Examples:

1
1 0
2
1 0
-1 0

</p>

outputFormat

Output a single integer – the number of distinct valid paths.

sample

1
1 0

1