17771번 - Constellation 다국어

문제

JOI 君は星空の観察が大好きな少年である.毎晩のように星空を観察しては,それぞれの星がどの星座 に属するのかを調べて楽しんでいる.

ある晩,JOI 君がいつものように星空を観察していると,見たことのない星を N 個発見した.これらの 星がどの星座に属するのかが気になった JOI 君は,夜空を写真に撮り,翌日図書館でこれらの星について 調べてみた.すると,これらの星はすべて星座 A か星座 B のどちらかに属することと,これらの星のうち いくつかの星がどちらに属しているかがわかった.だが,その他の星については,どちらの星座に属して いるかがわからなかった.JOI 君は,星座 A と星座 B を構成する星の集合として考えられるものが何通り あるかが気になった.なお,星の大きさは十分小さいので,点とみなしてよい.

ただし,星座とは,写真上で 1 つ以上の星と,星 2 つを結ぶ線分いくつかからなり,以下の条件を満た す.星 1 つのみからなるものも星座とみなすことに注意せよ.

• ある星座を構成する任意の 2 つの星は,写真上でその星座を構成する線分を辿ることで互いに到達す ることができる.
• ある星座を構成する線分と別の星座を構成する線分は交わらない.

また,JOI 君の発見した星は,以下の条件を満たす.

• どの 3 つの星も,写真上で同一直線上にない.
• どの星も星座 A または星座 B に属し,JOI 君の発見した星以外で星座 A または星座 B に属するもの は存在しない.

N 個の星の情報が与えられたとき,星座 A と星座 B を構成する星の集合として考えられるものの総数を 1 000 000 007 (= 10⁹ + 7) で割った余りを求めるプログラムを作成せよ.

입력

標準入力から以下の入力を読み込め.

• 1 行目には整数 N が書かれており,JOI 君の発見した星の数を表す.
• 続く N 行には,星の情報が書かれている.i + 1 行目 (1 ≤ i ≤ N) には,3 つの整数 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⁹ + 7) で割った余 りを 1 行で出力せよ.そのような星の集合が存在しない場合,0 を出力せよ.

제한

• 2 ≤ N ≤ 100 000 JOI 君の発見した星の数
• 0 ≤ X_i ≤ 10⁹, 0 ≤ Y_i ≤ 10⁹ 星 i の写真上での座標

힌트