## COCI '21 Contest 3 #5 Kućice

View as PDF

Points: 25 (partial)
Time limit: 0.5s
Memory limit: 512M

Problem type

Everyone knows that every other booth at the Zagreb Christmas Market was actually set up just by pulling the right strings. This year the authorities have decided to send an inspection to penalize the booths that were set up illegitimately.

There are booths, which can be represented by points in the plane, where no three of them lie on the same line. The authorities will identify the booths ruled by corruption and fence them off from the rest of the town. The fence will surround the mentioned booths, and it will form the shape of the smallest convex polygon containing all of them. In other words, the fence can be thought of as the boundary of the convex hull of the chosen set of points. Unfortunately, it's possible that some of the innocent booths become fenced off as well.

Before an on-site inspection, the authorities estimate that the probability of corruption of any particular booth is . Having this in mind, they wonder what is the expected number of booths that will end up being fenced off. The expected value is defined by multiplying the probability of a certain subset of booths being chosen by the number of booths fenced off in that choice and summing this up for all possible choices of the subset. Of course, if the chosen subset consists of less than three points, the convex hull is degenerate, i.e., a segment, point or the empty set.

It can be proven that the desired expected value can be written in the form , for some positive integer . The authorities would like to know the expected value, so they kindly ask you to compute the value of . Since the answer can be very large, you should print it modulo .

#### Input Specification

The first line contains a positive integer , the number of booths.

The of the next lines contains a pair of integers , which represent the and coordinates of the booth, respectively. No two booths have the same location.

No three booths will lie on the same line.

#### Output Specification

In the only line, print the number described above, modulo .

#### Constraints

110All points are on the boundary of the convex hull of all points and .
230All points except the first one are on the boundary of the convex hull of all points, which is in the interior, and , .
310
430

#### Sample Input 1

1
5 5

#### Sample Output 1

1

#### Explanation for Sample Output 1

There is a probability of that the first and only booth gets fenced off, so the expected value is .

#### Sample Input 2

3
-1 -1
1 -1
0 1

#### Sample Output 2

12

#### Explanation for Sample Output 2

There are eight possible choices for a subset, and the number of fenced off booths for those choices is . The expected value is then .

#### Sample Input 3

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

#### Sample Output 3

83