21816번 - 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$.

제한

힌트