P7529 [USACO21OPEN] Permutation G

Bessie has $N$ favorite distinct points on the 2D plane, and no three points are collinear. For each $1 \le i \le N$, the $i$-th point is given by two integers $x_i$ and $y_i$. Bessie draws some line segments among these points in the following way: - 1. She chooses a permutation $p_1, p_2, \dots, p_N$ of the $N$ points. - 2. She draws line segments between $p_1$ and $p_2$, between $p_2$ and $p_3$, and between $p_3$ and $p_1$. - 3. Then, for each integer $i$ from $4$ to $N$ in order, and for every $j < i$, she draws a line segment from $p_i$ to $p_j$ as long as this segment does not intersect any previously drawn segment (intersection at endpoints is allowed). Bessie notices that for every $i$, she draws exactly three new line segments. Compute the number of permutations she can choose in Step 1 that satisfy the property above, modulo $10^9 + 7$.

The first line contains $N$. The next $N$ lines each contain two space-separated integers $x_i$ and $y_i$.

Output one integer: the number of valid permutations modulo $10^9 + 7$.

#### Explanation for Sample 1 No permutation satisfies the property. #### Explanation for Sample 2 All permutations satisfy the property. #### Explanation for Sample 3 One valid permutation is $(0,0), (0,4), (4,0), (1,2), (1,1)$. For this permutation, - First, she draws line segments between each pair among $(0,0)$, $(0,4)$, and $(4,0)$. - Then she draws segments from $(1,2)$ to $(0,0)$, $(0,4)$, and $(4,0)$. - Finally, she draws segments from $(1,1)$ to $(1,2)$, $(4,0)$, and $(0,0)$.  ### Constraints $3 \le N \le 40$, $0 \le x_i, y_i \le 10^4$. Translated by ChatGPT 5