Problem Background

Users of Android phones are certainly familiar with gesture unlocking. The Android unlock screen consists of a $3 \times 3$ grid of points. By drawing a line on the screen that connects some of these points, one can form an unlock pattern. Examples are shown below:

Problem Description

When drawing the line, certain rules must be followed:
1. The number of connected points must not be less than $4$. Connecting only two or three points will result in an error.
2. The line between two points cannot be curved.
3. Each point can only be "used" once; it cannot be repeated. "Used" here means that a point is touched by the finger, turning it green.
4. The line between two points cannot "cross" another point unless that point has already been "used".

For the last rule, refer to the explanation in the following image. The left two images violate this rule; the right two images (sequences $2 \rightarrow 4 \rightarrow 1 \rightarrow 3 \rightarrow 6$ and $6 \rightarrow 5 \rightarrow 4 \rightarrow 1 \rightarrow 9 \rightarrow 2$) do not violate the rule, as the points being crossed have already been used.

Now, engineers wish to improve the unlock screen by varying the number of points and their positions, no longer maintaining a $3 \times 3$ grid shape, but keeping the drawing rules unchanged.

Calculate the total number of valid drawing patterns on the new unlock screen.

Input Format

The first line of input contains an integer $n$, representing the number of points.

The next $n$ lines each contain two integers $x_i$ and $y_i$, separated by spaces, representing the coordinates of each point.

Output Format

Output a single line containing the number of valid patterns modulo $10^8+7$.

Sample Input and Output

Sample Input #1

4
0 0
1 1
2 2
3 3

Sample Output #1

8

Sample Input #2

4
0 0
0 1
0 2
1 0

Sample Output #2

18

Notes

Sample Explanation 1

Let the four points be numbered from $1$ to $4$. The valid patterns include $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$, $2 \rightarrow 1 \rightarrow 3 \rightarrow 4$, $3 \rightarrow 2 \rightarrow 1 \rightarrow 4$, $2 \rightarrow 3 \rightarrow 1 \rightarrow 4$, and their mirrored versions.

Data Range

• For $30\%$ of the data, $1 \le n \le 10$.
• For $100\%$ of the data, $-1000 \le x_i, y_i \le 1000$, $1 \le n < 20$. All points have distinct coordinates.

见题面 Input 部分

见题面 Output 部分