Expected Enclosed Stalls

There are n stalls at a Christmas market. Each stall is represented as a point on the 2D plane with coordinates \( (x_i,y_i) \). Each stall independently violates the rules with probability \( 50\% \). All violating stalls are enclosed by a fence whose shape is defined as the boundary of the convex hull of the points corresponding to the violating stalls. Note that some innocent (non‐violating) stalls can also be enclosed by the fence. When the number of violating stalls is less than 3, the convex hull degenerates to a line segment, a point, or is empty.

Let the number of stalls enclosed (i.e. those lying in or on the fence) be \( f(S) \) for a given set \( S \) of violating stalls. Since each stall is chosen independently with probability \( 1/2 \), the expected value of the enclosed stalls is \[ E=\frac{1}{2^n}\sum_{S\subseteq\{1,2,...,n\}}f(S). \] It can be shown that the answer can be expressed in the form \( \frac{m}{2^n} \), where \( m \) is a positive integer. Therefore, you only need to output \( m \) modulo \( 10^9+7 \).

Note: When computing the convex hull, if there are fewer than 3 violating stalls the fence is taken as the degenerate convex hull (a point if there is 1 stall, or the segment joining two points if there are 2 stalls). A stall is considered enclosed if it lies on or inside the fence.

inputFormat

The first line contains an integer \( n \) denoting the number of stalls. Each of the next \( n \) lines contains two integers \( x_i \) and \( y_i \), representing the coordinates of the \( i \)-th stall.

outputFormat

Output a single integer representing \( m \) modulo \( 10^9+7 \), where the expected number of enclosed stalls is \( \frac{m}{2^n} \).

sample

3
0 0
1 0
0 1

12