시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 56 21 15 46.875%

문제

한국의 모든 코더들은 대구과학고 방향으로 하루에 5번 절을 해야 한다. 대구과학고에는 코딩의 신 시제연이 있기 때문이다. 그는 O($N^3$) 알고리즘을 O($N^2$)으로 바꿀 수 있고, 아무리 어려운 문제라도 보자마자 바로 풀어버린다.

이렇게 위대한 제연이와 감히 맞먹으려 하는 사람들이 있었으니, 바로 경기과학고의 <나는 코더다> 동아리였다. 그들은 제연이에게 하루 5번 절을 하지 않는 유일한 코더들이었다. 제연이는 자신에게 절을 하지 않는 오만방자한 사람들이 있다는 충격적인 사실을 듣고, 자신의 힘을 보여주기 위해 경기과학고를 침공하기로 했다.

5000만 신자들을 이끌고 경기과학고에 쳐들어온 제연이는 손쉽게 항복을 받아냈지만, 아직도 분이 풀리지 않은 제연이는 경기과학고 주변에 자신의 코드포스 핸들 'tlwpdus'가 새겨진 울타리를 둘러 자신의 위상을 만천하에 떨치려 한다.

경기과학고 주변에는 말뚝을 꽂을 수 있는 지점이 $N$개가 있는데, 제연이는 이 지점들 중 적어도 3개를 포함하는 임의의 부분집합을 골라 말뚝을 꽂고, 말뚝들이 이루는 볼록 껍질 (Convex Hull) 모양의 울타리를 치려고 한다. 제연이는 돈도 많고 시간도 많으므로, 만들 수 있는 모든 울타리 모양을 하루에 한 개씩 만들려고 한다.

제연이는 자신이 이 과업을 모두 수행하는 데 며칠이 걸리는지 이미 정확히 알고 있다. 그리고 경기과학고에서 정보 좀 한다는 여러분이 이 어려운 문제를 과연 풀어낼 수 있을지 궁금해하고 있다. 이 문제를 풀어 경기과학고의 저력을 보여주자!

입력

첫 번째 줄에는 말뚝을 박을 수 있는 점의 수 $N$ ($3 \le N \le 300$) 이 주어진다.

다음 $N$개의 줄에는 각 점의 좌표 값 $x_i$와 $y_i$가 공백을 사이에 두고 주어진다. ($|x_i|, |y_i| \le 10^9$)

세 점이 한 직선 위에 없음이 보장된다.

출력

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

예제 입력 1

4
1 1
1 2
2 1
2 2

예제 출력 1

5