Triangulated Permutations

Bessie has \(N\) distinct favorite points on the 2D plane, with no three being collinear. Each point \(i\) is given by a pair of integers \(x_i\) and \(y_i\).

She performs the following procedure:

1. Choose a permutation \(p_1, p_2, \dots, p_N\) of the \(N\) points.
2. Draw segments connecting \(p_1\) to \(p_2\), \(p_2\) to \(p_3\), and \(p_3\) to \(p_1\) (forming a triangle).
3. For each \(i\) from 4 to \(N\), for every \(j < i\), draw a segment from \(p_i\) to \(p_j\) if and only if this segment does not intersect any previously drawn segment (intersections at endpoints are allowed).

Bessie notices that in this process every time she adds a new point \(p_i\) (for any \(i\)), exactly three new segments are drawn. It can be shown that this is possible if and only if:

• The first three points \(p_1, p_2, p_3\) are exactly the three vertices of the convex hull of all \(N\) points.
• All other \(N-3\) points lie strictly inside the triangle formed by these three extreme points.

Under these conditions, the drawing procedure is equivalent to inserting interior points into a triangulation: when a new point is inserted into one of the triangular faces, it connects to the three vertices of that face, thereby adding exactly three segments.

Your task is to compute the number of valid permutations (i.e. the number of ways to order the points) that satisfy the above property. Since the answer can be very large, output it modulo \(10^9+7\).

Hint: If the convex hull of the \(N\) points does not consist of exactly 3 points, then no valid permutation exists. Otherwise, the valid permutations are those in which the three extreme points (forming the outer triangle) occupy the first three positions (in any order) and the remaining \(N-3\) points can appear in any order. Thus, the answer is \(6\times (N-3)! \pmod{10^9+7}\).

inputFormat

The first line contains an integer \(N\) (\(3 \le N \le 10^5\)). Each of the next \(N\) lines contains two integers \(x_i\) and \(y_i\) (\(|x_i|, |y_i| \le 10^9\)) representing the coordinates of a point.

outputFormat

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

sample

3
0 0
1 0
0 1

6