별자리

시간 제한1초메모리 제한512 MB

요약

별자리 A와 B에 속하는 별의 집합을 정할 때, 두 집합이 각각 연결되고 선분이 서로 교차하지 않도록 하는 경우의 수를 구한다.

난이도: 어려움10점 중 9점
유형: 기하, 조합론, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

JOI 군은 별이 총총한 밤하늘을 관찰하는 것을 좋아하는 소년이다. JOI 군은 거의 매일 밤 별자리를 관찰하며 별자리가 어떻게 생겼는지 알아보는 것을 좋아한다.

어느 날 밤, JOI 군은 하늘에서 지금까지 본 적 없는 별 $N$ 개를 발견했다. JOI 군은 이 별들이 어떤 별자리에 속하는지 궁금해져서 밤하늘을 사진으로 찍었고, 다음 날 도서관에서 이 별들에 대해 조사했다. 그 결과, 이 별들은 모두 별자리 A 또는 별자리 B 중 하나에 속한다는 것과, 그중 일부 별이 어느 별자리에 속하는지는 알아냈다. 하지만 나머지 별들에 대해서는 어느 별자리에 속하는지 알 수 없었다. JOI 군은 별자리 A와 별자리 B를 구성하는 별의 집합이 몇 가지나 가능한지 궁금해졌다. 별의 크기는 충분히 작아서 점으로 생각해도 된다.

별자리란, 사진 위에서 별 하나 이상과 별 두 개를 잇는 선분 몇 개로 이루어져 있으며 다음 조건을 만족한다. 별 하나만으로 이루어진 것도 별자리로 본다는 것에 주의하자.

어떤 별자리를 구성하는 임의의 두 별은 사진 위에서 그 별자리를 구성하는 선분을 따라 서로 도달할 수 있다.
어떤 별자리를 구성하는 선분과 다른 별자리를 구성하는 선분은 교차하지 않는다.

또한 JOI 군이 발견한 별은 다음 조건을 만족한다.

어떤 세 별도 사진 위에서 같은 직선 위에 있지 않다.
모든 별은 별자리 A 또는 별자리 B에 속하며, JOI 군이 발견한 별 외에 별자리 A 또는 별자리 B에 속하는 것은 존재하지 않는다.

$N$ 개의 별 정보가 주어졌을 때, 별자리 A와 별자리 B를 구성하는 별의 집합으로 가능한 것의 총수를 $1\ 000\ 000\ 007$ ( $=10^9+7$ )로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

표준 입력에서 다음 입력을 읽어들인다.

첫째 줄에는 정수 $N$ 이 쓰여 있으며, JOI 군이 발견한 별의 수를 나타낸다.
다음 $N$ 개 줄에는 별의 정보가 쓰여 있다. $i+1$ 번째 줄 ( $1 \le i \le N$ )에는 세 개의 정수 $X_i, Y_i, C_i$ 가 공백으로 구분되어 쓰여 있다. $X_i, Y_i$ 는 별 $i$ 의 사진 위에서의 좌표가 $(X_i, Y_i)$ 임을 나타낸다. $C_i$ 는 별 $i$ 가 별자리 A와 별자리 B 중 어디에 속하는지를 나타낸다.
- $C_i = 0$ 인 경우 별 $i$ 가 어느 별자리에 속하는지 알 수 없음을 나타낸다.
- $C_i = 1$ 인 경우 별 $i$ 가 별자리 A에 속함을 나타낸다.
- $C_i = 2$ 인 경우 별 $i$ 가 별자리 B에 속함을 나타낸다.

출력

별자리 A와 별자리 B를 구성하는 별의 집합으로 가능한 것의 총수를 $1\ 000\ 000\ 007$ ( $=10^9+7$ )로 나눈 나머지를 한 줄에 출력한다. 그러한 별의 집합이 존재하지 않는 경우, 0을 출력한다.

제한

$2 \le N \le 100\ 000$ . JOI 군이 발견한 별의 수
$0 \le X_i \le 10^9$ , $0 \le Y_i \le 10^9$ . 별 $i$ 의 사진 위에서의 좌표

예제1

예제 1
입력
```
4
1 1 1
2 1 1
1 2 0
2 2 2
```
예상 출력
```
2
```