Problem Statement

We have $N$ points $P_1, P_2, \dots, P_N$ on a plane. The coordinates of $P_i$ is $(X_i, Y_i)$. We know that no three points lie on the same line.

For a subset $S$ of $\{ P_1, P_2, \dots, P_N \}$ with at least three elements, let us define the convex hull of $S$ as follows:

• The convex hull is the convex polygon with the minimum area such that every point of $S$ is within or on the circumference of that polygon.

Find the number, modulo $(10^9 + 7)$, of subsets $S$ such that the area of the convex hull is an integer.

Constraints

• $3 \leq N \leq 80$
• $0 \leq |X_i|, |Y_i| \leq 10^4$
• No three points lie on the same line.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print the answer. Note that you are asked to find the count modulo $(10^9 + 7)$.