시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

Bobo found $n$ points on the plane. He randomly picks a subset of points (each subset has equal probability to be picked), and would like to know the expectation of the size of convex hull.

Note that the convex hull should not contain two duplicate points or three collinear points.

입력

The first line contains an integer $n$ ($1 \leq n \leq 2000$).

Each of following $n$ lines contains $2$ integers $x_i, y_i$ which denotes a point $(x_i, y_i)$ ($0 \leq x_i, y_i \leq 10^9$).

출력

If the expectation is $E$, a single integer denotes $E \cdot 2^n \bmod (10^9+7)$.

예제 입력 1

3
0 0
0 1
1 0

예제 출력 1

12

예제 입력 2

3
0 0
0 1
0 2

예제 출력 2

11