Permutation

문제

Bessie has $NN$ ($3\le N\le 403\backslash le\; N\backslash le\; 40$) favorite distinct points on a 2D grid, no three of which are collinear. For each $1\le i\le N1\backslash le\; i\backslash le\; N$, the $ii$-th point is denoted by two integers $x_{i}x\_i$ and $y_{i}y\_i$ ($0\le x_i,y_i\le {10}^{4}0\backslash le\; x\_i,y\_i\backslash le\; 10^4$).

Bessie draws some segments between the points as follows.

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

Bessie notices that for each $ii$, 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+710^9+7$.

입력

The first line contains $NN$.

Followed by $NN$ lines, each containing two space-separated integers $x_{i}x\_i$ and $y_{i}y\_i$.

출력

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

4
0 0
0 4
1 1
1 2

0

4
0 0
0 4
4 0
1 1

24

5
0 0
0 4
4 0
1 1
1 2

96