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 (= 109 + 7) で割った余りを求めるプログラムを作成せよ．

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

• 1 行目には整数 N が書かれており，JOI 君の発見した星の数を表す．

• 続く N 行には，星の情報が書かれている．i + 1 行目 (1 ≤ i ≤ N) には，3 つの整数 Xi, Yi, Ci が空白区 切りで書かれている．Xi, Yi は星 i の写真上での座標が (Xi, Yi) であることを表す．Ci は星 i が星座 A と星座 B のどちらに属しているかを表す．

  • Ci = 0 の場合は星 i がどちらの星座に属するかわからないことを表す．
  • Ci = 1 の場合は星 i が星座 A に属していることを表す．
  • Ci = 2 の場合は星 i が星座 B に属していることを表す．

星座 A と星座 B を構成する星の集合として考えられるものの総数を 1 000 000 007 (= 109 + 7) で割った余 りを 1 行で出力せよ．そのような星の集合が存在しない場合，0 を出力せよ．

• 2 ≤ N ≤ 100 000 JOI 君の発見した星の数
• 0 ≤ Xi ≤ 109, 0 ≤ Yi ≤ 109 星 i の写真上での座標