Description

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

Input Format

The first line contains $N$.

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

Output Format

Output one integer: the number of valid permutations modulo $10^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

Hint

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