Informatica Online Judge

  별자리 (Constellation) [0845 / 034D]

Time Limit(Test case) : 1500(ms)
Number of users who solved : 5   Total Tried : 11


The Champion of this Problem (C++) : ainta - 22ms / 1781byte
My Best Submission (C++) : N/A

[]

Background

경곽이는 밤하늘을 관찰하는 것을 좋아한다.

매일밤 별들을 관찰하며 각각의 별들이 어느 별자리에 속하는지 조사하는 것을 즐긴다.



어느날 밤 경곽이는 평소처럼 별자리를 관찰하고 있었다. 그런데 처음 보는 별을 N개 발견하였다.

이 별들은 어느 별자리에 속하는지 궁금해 진 경곽이는 그 별들을 사진으로 찍고, GSHS도서관으로 가서 이 별자리에 대해서 조사했다.

그 결과는 이 별들은 모두 별자리 A와 별자리 B 중 하나에 속한다는 사실과 이 별들 중 몇 개의 별들이 어느 별자리에 속하는지를 알 수 있었다.

하지만 그 외의 별들에 대해서는 어느 별자리에 속하는지 알 수 없었다.

경곽이는 별자리 A와 별자리 B를 구성하는 별의 집합으로 생각될 수 있는 것이 몇 가지나 가능한지 궁금해졌다.

즉, 별의 크기는 충분히 작으므로 점으로 생각할 수 있다.

단, 별자리라는 것은 사진 상에서 1개 이상의 별과 별 2개를 연결하는 간선이 몇 개로 구성되어 있으며, 다음 조건을 만족한다.

별 1개로 구성된 별자리도 있음에 유의한다.

- 어느 별자리를 구성하는 임의의 2개의 별은 사진상에서 그 별자리를 구성하는 간선을 따라가면 서로 도달할 수 있다.
- 어느 별자리를 구성하는 간선과 그 외의 별자리를 구성하는 간선은 교차하지 않는다.

또 경곽이가 발견한 별은 다음 조건을 만족한다.

- 어느 3개의 별도 사진상에서 동일 직선상에 존재하지 않는다.
- 모든 별은 별자리 A 또는 별자리 B에 속하고, 경곽이가 발견한 별 이외에 별자리 A 혹은 별자리 B에 속하는 별은 없다.

N개의 별의 정보가 주어질 때, 별자리 A와 별자리 B를 구성하는 별의 집합으로 생각될 수 있는 경우의 수를 1 000 000 007로 나눈 나머지를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 별의 수를 나타내는 정수 N이 주어진다.
두 번째 줄부터 N줄에 걸쳐서 x, y, c가 공백으로 구분되어 입력된다. 여기서 (x, y)는 별의 좌표이고, c는 별자리 A에 속하는지 별자리 B에 속하는지를 나타낸다.

만약
c = 0이면 어느별자리에 속하는지 모르는 것을 의미한다.
c = 1이면 그 별이 별자리 A에 속한다는 의미이다.
c = 2이면 그 별이 별자리 B에 속한다는 의미이다.

각 값들의 정의역은 다음과 같다.

2 <= N <= 100 000
0 <= x, y <= 1 000 000 000 (정수)
c ∈ { 0, 1, 2 }

Output

첫 번째 줄에 가능한 별자리 A와 별자리 B의 경우의 수를 1 000 000 007로 나눈 나머지를 출력한다.

IO Example

입력
4
1 1 1
2 1 1
1 2 0
2 2 2

출력
2

* 설명
이 입력의 경우 다음 그림에 대응한다. 단 검은 점은 별자리 A, 힌색 점은 별자리 B에 속하는 별을 X는 어느 별자리에 속하는지 알 수 없는 경우를 나타낸다.



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]