Permutation

Bessie has $N$ ($3\le N\le 40$) favorite distinct points on a 2D grid, no three of which are collinear. For each $1\le i\le N$, the $i$-th point is denoted by two integers $x\_i$ and $y\_i$ ($0\le x\_i,y\_i\le 10^4$).

Bessie draws some segments between the points as follows.

1. She chooses some permutation $p\_1,p\_2,\ldots,p\_N$ of the $N$ points.
2. She draws segments between $p\_1$ and $p\_2$, $p\_2$ and $p\_3$, and $p\_3$ and $p\_1$.
3. Then for each integer $i$ from $4$ to $N$ in order, she draws a line segment from $p\_i$ to $p\_j$ for all $j\<i$ such that the segment does not intersect any previously drawn segments (aside from at endpoints).

Bessie notices that for each $i$, she drew exactly three new segments. Compute the number of permutations Bessie could have chosen on step 1 that would satisfy this property, modulo $10^9+7$.

The first line contains $N$.

Followed by $N$ lines, each containing two space-separated integers $x\_i$ and $y\_i$.

The number of permutations modulo $10^9+7$.