울타리 침공

주어진 점들 중 3개 이상을 골라 만들 수 있는 서로 다른 볼록 껍질 다각형의 개수를 10^9+7로 나눈 나머지를 구한다.

어려움8기하조합론동적 계획법정렬아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

알고리즘으로 이름난 코더가 어느 과학고에 있다. 그는 O(N3)O(N^3) 알고리즘을 O(N2)O(N^2)으로 줄이고, 어려운 문제도 보자마자 풀어낸다.

이웃 과학고의 프로그래밍 동아리만은 그 실력을 인정하지 않았다. 소식을 들은 코더는 실력을 보여주려고 그 학교로 쳐들어가 손쉽게 항복을 받아냈다. 그래도 분이 풀리지 않아 학교 둘레에 자기 핸들을 새긴 울타리를 둘러 위세를 떨치기로 했다.

학교 주변에는 말뚝을 꽂을 수 있는 지점이 NN개 있다. 코더는 이 지점 중 3개 이상을 골라 그 자리에 말뚝을 꽂고, 말뚝이 이루는 볼록 껍질(convex hull) 모양으로 울타리를 친다. 돈도 시간도 많으니 만들 수 있는 울타리 모양을 하루에 하나씩 전부 만들 생각이다.

서로 다른 울타리 모양이 몇 가지인지 세어라. 두 울타리가 평면에서 같은 영역을 덮으면 같은 모양으로 본다.

입력

첫 줄에 말뚝을 꽂을 수 있는 지점의 수 NN (3N3003 \le N \le 300)이 주어진다.

다음 NN개 줄에는 각 지점의 정수 좌표 xix_iyiy_i가 공백을 사이에 두고 주어진다. (xi,yi109|x_i|, |y_i| \le 10^9)

세 지점이 한 직선 위에 있는 경우는 없다.

출력

첫 줄에 서로 다른 울타리 모양의 개수를 109+710^9+7로 나눈 나머지를 출력한다.