#1535. 星座

星座

题目描述

题目译自 JOISC 2012 Day2 T2「星座

JOI 君是一个十分喜欢观察星空的少年,他每天晚上都观察星空,并且以找出每颗星星属于哪个星座为乐。

一天晚上,JOI 君像往常一样观察星空,并看到了他从没见到的 NN 颗星星。JOI 想知道这些星星属于哪些星座,于是拍了一张星空的照片。第二天,他去了图书馆查找。实际上,这些星星都属于星座 A 或星座 B,而一些星星知道它属于星座 A 和 B 中的某一个,另一些不知道。JOI 君想知道用这些星星组成星座 A 和星座 B 的情况总数。由于星星的大小足够小,因此可以看成一个点。

星座是由照片上的一颗或多颗星星两两连成的线段组成的。注意仅由一颗星星组成的星座也被看做一个星座。

  • 这些线段可以让星座中任意两颗星彼此可达;
  • 构成一个星座的线段不与构成另一星座的线段相交。

此外,JOI 君发现星星满足以下条件:

  • 任意三颗星星均不共线;
  • 星星只属于星座 A 或星座 B 的一种,JOI 君发现的星星没有属于除星座 A 和星座 B 之外的星座。

给出 NN 颗星星的信息,求由这些星星组成星座 A 和星座 B 的情况总数对 109+710^9+7 取模的值。

输入格式

第一行一个整数 NN,表示 JOI 君看到的星星总数;

接下来 NN 行,每行三个数 Xi,Yi,CiX_i,Y_i,C_i,表示这颗星星的坐标为 (Xi,Yi)(X_i,Y_i)CiC_i 表示这颗星星属于哪个星座:

  • Ci=0C_i=0 表示这颗星星不知道属于星座 A 还是属于星座 B;
  • Ci=1C_i=1 表示这颗星星属于星座 A;
  • Ci=2C_i=2 表示这颗星星属于星座 B。

输出格式

输出一行一个整数,表示用这些星星组成星座 A 和星座 B 的方案数,对 109+710^9+7 取模。若不存在任何组成方式,则输出 00

样例

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

对于这组输入样例,对应图形如下图,其中,属于星座 A 的点标为黑色,属于星座 B 的点标为白色,不知道属于哪个星座的点标为 ×\times

constellation1.png

当第三颗星星属于星座 A 或星座 B 时,该组样例答案为 22。下图是两种答案情况。注意,当第三颗星星属于星座 A 时,有多种方法可以绘制线段,但是只看成一种。

constellation2.png

数据范围与提示

10%10\% 的分数满足 N10N\le 10

50%50\% 的分数满足 N300N\le 300

对于全部数据,2N105,0Xi,Yi109,0Ci22\le N\le 10^5,0\le X_i,Y_i\le 10^9,0\le C_i\le 2