Proper Polygon Cuts

Ingrid owns a shop selling convex polygons whose vertices have integer coordinates. Her customers value polygons that can be \(\textbf{cut}\) in a "proper way": a straight cut connecting two nonadjacent vertices such that both resulting parts are non‐empty and each has an integer area. In this problem, you are given a convex polygon and are asked to compute the number of proper cuts.

Definition: A cut is defined by choosing two vertices \(i\) and \(j\) (with \(j\) not equal to \(i\pm 1\) modulo \(n\), where \(n\) is the number of vertices) to form a line segment (a diagonal). This diagonal splits the polygon into two polygons. If the doubled area (using the shoelace formula) of both parts is even (so that the area itself is an integer), the cut is called proper.

The overall polygon may have a non‐integer area, but only those cuts producing two subpolygons with integer areas are counted. Note that if the doubled area of the given polygon is odd then no valid cut exists.

For example, in one case there are three proper cuts and in another there are two.

Your task is to write an automatic tool to determine the number of proper cuts for a given convex polygon.

inputFormat

The first line contains an integer \(n\) (the number of vertices, \(4 \le n \le 500\)). The next \(n\) lines each contain two integers \(x_i\) and \(y_i\) representing the coordinates of the \(i\)th vertex. The vertices are listed in counterclockwise order.

outputFormat

Output a single integer: the number of proper cuts of the polygon.

sample

4
0 0
1 0
1 1
0 1

0