Constellation(星座) - joi2012-day2

時間制限: 1秒

メモリ制限: 64MB

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

制限

`2 \leqq N \leqq 100\,000`	JOI 君の発見した星の数
`0 \leqq X_i \leqq 10^9, 0 \leqq Y_i \leqq 10^9`	星 `i` の写真上での座標

入力

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

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

採点基準

採点用データのうち，配点の 10% 分については N \leqq 10 を満たす．
採点用データのうち，配点の 50% 分については N \leqq 300 を満たす．

入出力例

入力例1	出力例1
`4 1 1 1 2 1 1 1 2 0 2 2 2`	`2`

この入力例は，次の図に対応している．ただし，黒い点は星座 A に属する星を，白い点は星座 B に属する星を，×印はどちらの星座に属するかわからない星を，それぞれ表す．

この入力に対する答えは，星 3 が星座 A に属する場合と星座 B に属する場合の 2 通りであり，それぞれの場合の星座の図の一例を以下に示す．星 3 が星座 A に属する場合，星座 A の線分の引き方は何通りか考えられるが，それらすべてをまとめて 1 通りと数えることに注意せよ．