Description

There are $n$ stalls in a Christmas market. Each stall can be seen as a point in the 2D Cartesian coordinate system, with coordinates $x_i, y_i$.

Now each stall violates the rules with probability $50\%$. All violating stalls will be enclosed by a fence, whose shape is the boundary of the convex hull of the points corresponding to all violating stalls. Of course, some innocent stalls that do not violate the rules may also be enclosed. When the number of violating stalls is less than $3$, the convex hull clearly degenerates into a line segment, a point, or the empty set.

Find the expected number of stalls that are enclosed. It can be proven that the answer can be written as $\frac{m}{2^n}$, where $m$ is a positive integer. Therefore, you only need to output $m \bmod (10^9+7)$.

Input Format

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

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

Output Format

Output $m \bmod (10^9+7)$.

1
5 5

1

3
-1 -1
1 -1
0 1

12

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

83

Hint

Sample 1 Explanation

The only stall violates the rules with probability $50\%$, so the expected value is $\frac{1}{2}$.

Sample 2 Explanation

There are $8$ possible violation cases, and the numbers of enclosed stalls in each case are $0, 1, 1, 1, 2, 2, 2, 3$, respectively. Therefore, the expected value is $\frac{1}{8}(0+1+1+1+2+2+2+3)=\frac{12}{8}$.

Constraints

This problem uses bundled subtasks.

• Subtask 1 (10 pts): Every point lies on the boundary of the convex hull formed by all points, and $n \ge 3$.
• Subtask 2 (30 pts): Except for the first point, every point lies 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 testdata, $1 \le n \le 1000$, $|x_i|, |y_i| \le 10^6$.

Notes

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

The score of this problem follows the original COCI settings, with a full score of $110$.

Translated by ChatGPT 5