문제
평면 상에 3가지 종류의 점이 N개 있다. 각 점은 빨간색으로 칠해져 있거나, 파란색으로 칠해져 있거나, 아직 아무 색도 칠해져 있지 않을 수도 있다.
아직 색이 정해지지 않은 점들을 각각 빨간색 혹은 파란색으로 칠하고 싶다. 하지만 그냥 칠하는 것은 재미가 없기에, 다음 규칙을 추가하기로 했다.
"색을 모두 칠했을 때, 파란 점들로 만든 스패닝 트리와 빨간 점들로 만든 스패닝 트리가 겹치지 않는 방법이 적어도 하나 이상 있어야 한다."
이때 스패닝 트리를 이루는 간선들은 모두 어떤 점과 점 사이를 잇는 선분 모양이어야 한다.
위 규칙을 만족하면서 아직 색칠이 안된 정점에 색을 칠하는 경우의 수를 구하시오.
입력
첫 줄에 정점의 개수 N(2<=N<=100000)이 주어진다.
다음 줄부터 N줄에 걸쳐 i번째 정점의 정보 xi, yi, ci가 주어진다.
(xi, yi)는 i번째 정점의 위치이며, ci=1이면 빨간색, ci=2이면 파란색, ci=0이면 아직 색이 칠해져 있지 않은 상태를 뜻한다.
이때 0<=xi,yi<=10^9를 만족한다.
또, 어떤 세 정점도 한 직선 위에 놓여있지 않다.
출력
규칙을 만족하면서 아직 색칠이 안된 정점에 색을 칠하는 경우의 수를 10^9+7로 나눈 나머지를 출력하시오.
예제
4
1 1 1
2 1 1
1 2 0
2 2 2
2
출처
JOISC 2011/2012
로그인해야 코드를 작성할 수 있어요.