23045번 - 별 보는 교준이

문제

교준이는 이차원 좌표평면의 밤하늘을 바라보고 있다. 지금 하늘에는 서로 다른 위치에 $N$개의 별이 반짝이고 있고, $i$번 별의 위치는 $\left( X_i, Y_i \right)$이다.

교준이는 다음 조건을 모두 만족하도록 $N$개의 별을 두 개의 별자리, A 별자리와 B 별자리로 구분하고자 한다. 교준이가 사는 세상에서 별은 크기가 없는 고정된 점임에 유의하라.

• 각 별은 A 별자리와 B 별자리 중에서 정확히 하나의 별자리에 속한다.
• A 별자리 혹은 B 별자리에 속하는 별은 모두 교준이가 바라보고 있는 $N$개의 별 중 하나이다.
• A 별자리와 B 별자리는 각각 적어도 하나의 별을 가진다.
• A 별자리에 속한 별과 B 별자리에 속한 별을 서로 분리하는, $N$개의 별 중 어느 하나도 지나지 않는 밤하늘 위의 직선이 존재한다.

위의 조건을 모두 만족하도록 $N$개의 별을 A 별자리와 B 별자리로 구분하는 경우의 수를 구하라.

입력

첫째 줄에 정수 $N$이 주어진다. (2ドル \le N \le 1,500円$)

둘째 줄부터 $N$개의 줄에 걸쳐, $N$개의 별에 대한 정보가 주어진다. $(i+1)$번째 줄에는 두 정수 $X_i,ドル $Y_i$가 주어진다. (1ドル \le i \le N,ドル $\left| X_i \right| \le 10^8,ドル $\left| Y_i \right| \le 10^8$)

출력

첫째 줄에 경우의 수를 10ドル^9 + 7$로 나눈 나머지를 출력한다.

제한

힌트

첫째 예제의 경우, 별을 구분하는 방법은 총 6가지다. 속이 찬 빨간 원과 속이 빈 파란 원은 각각 A 별자리와 B 별자리에 속하는 별을 의미한다.

마지막 예제를 그림으로 나타내면 아래와 같다.