Problem Description

Bessie has \( N \) favorite distinct points on a 2D plane, where no three points are collinear. For each \( 1 \le i \le N \), the \( i \)-th point is represented by two integers \( x_i \) and \( y_i \).

Bessie draws some segments between these points as follows:

1. She chooses a permutation \( p_1, p_2, \dots, p_N \) of these \( N \) points.
2. She draws segments between points \( 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 \), for all \( j < i \), she draws a segment from \( p_i \) to \( p_j \), as long as this segment does not intersect with any already drawn segments (except at endpoints).

Bessie notices that for each \( i \), she draws exactly three new segments. Calculate the number of permutations Bessie can choose at the first step that satisfy these properties, modulo \( 10^9 + 7 \).

Input Format

The first line of input contains \( N \).

The following \( N \) lines each contain two space-separated integers \( x_i \) and \( y_i \).

Output Format

Output a single integer representing the number of valid permutations modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

4
0 0
0 4
1 1
1 2

Sample Output #1

0

Sample Input #2

4
0 0
0 4
4 0
1 1

Sample Output #2

24

Sample Input #3

5
0 0
0 4
4 0
1 1
1 2

Sample Output #3

96

Notes

Sample 1 Explanation

No permutation satisfies the properties.

Sample 2 Explanation

All permutations satisfy the properties.

Sample 3 Explanation

One permutation that satisfies the properties is \((0,0), (0,4), (4,0), (1,2), (1,1)\). For this permutation:

• Initially, she draws segments between \((0,0), (0,4)\) and \((4,0)\).
• Then she draws segments from \((1,2)\) to \((0,0), (0,4), (4,0)\).
• Finally, she draws segments from \((1,1)\) to \((1,2), (4,0), (0,0)\).

Data Range and Constraints

\( 3 \le N \le 40 \), \( 0 \le x_i, y_i \le 10^4 \)

见题面 Input 部分

见题面 Output 部分