Problem Description

In the Christmas market, there are $n$ stalls. Each stall can be abstracted as a point in the Cartesian coordinate system with coordinates $x_i, y_i$.

Each stall has a $50\%$ chance of being in violation. All violating stalls will be enclosed by a fence, which is the boundary of the convex hull formed by the points corresponding to the violating stalls. Naturally, some innocent stalls that are not in violation might also be enclosed. When the number of violating stalls is less than $3$, the convex hull will obviously degenerate into a line segment, a point, or an empty set.

Calculate the expected number of stalls that will be enclosed. It can be proven that the answer can be expressed as $\frac{m}{2^n}$, where $m$ is a positive integer. Therefore, you only need to output the value of $m$ modulo $10^9+7$.

Input Format

The first line contains a positive integer $n$, representing the number of stalls.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the stalls. The data guarantees that no two stalls have the same coordinates and no three stalls are collinear.

Output Format

Output the value of $m$ modulo $10^9+7$.

Sample Input and Output

Sample Input #1

1
5 5

Sample Output #1

1

Sample Input #2

3
-1 -1
1 -1
0 1

Sample Output #2

12

Sample Input #3

5
0 0
-1 0
2 -1
3 2
0 3

Sample Output #3

83

Notes/Hints

[Sample 1 Explanation]

The only stall has a $50\%$ chance of being in violation, so the expected value is $\frac{1}{2}$.

[Sample 2 Explanation]

There are $8$ possible scenarios of violations, and the number of enclosed stalls in each scenario is $0, 1, 1, 1, 2, 2, 2, 3$. Thus, the expected value is $\frac{1}{8}(0+1+1+1+2+2+2+3)=\frac{12}{8}$.

[Data Range and Constraints]

This problem uses subtask-based testing.

• Subtask 1 (10 pts): Each point is on the boundary of the convex hull formed by all points, and $n \ge 3$.
• Subtask 2 (30 pts): Except for the first point, each point is on the boundary of the convex hull formed by all points, and $n \ge 4$, $x_1=y_1=0$.
• Subtask 3 (10 pts): $1 \le n \le 15$.
• Subtask 4 (30 pts): $1 \le n \le 100$.
• Subtask 5 (30 pts): No special restrictions.

For $100\%$ of the data, $1 \le n \le 1000$, $|x_i|, |y_i| \le 10^6$.

[Hint and Attribution]

This problem is translated from COCI 2021-2022 CONTEST #3 Task 5 Kućice.

The score for this problem is set according to the original COCI problem, with a maximum score of $110$.

见题面 Input 部分

见题面 Output 部分