시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

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 の写真上での座標

예제 입력 1

4
1 1 1
2 1 1
1 2 0
2 2 2

예제 출력 1

2

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

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

星 3 が星座 A に属する場合

星 3 が星座 B に属する場合