题目描述

题目译自 JOISC 2012 Day2 T2「星座」

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

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

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

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

此外，JOI 君发现星星满足以下条件：

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

给出 $N$ 颗星星的信息，求由这些星星组成星座 A 和星座 B 的情况总数对 $10^9+7$ 取模的值。

输入格式

第一行一个整数 $N$，表示 JOI 君看到的星星总数；

接下来 $N$ 行，每行三个数 $X_i,Y_i,C_i$，表示这颗星星的坐标为 $(X_i,Y_i)$，$C_i$ 表示这颗星星属于哪个星座：

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

输出格式

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

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

2

数据范围与提示

有 $10\%$ 的分数满足 $N\le 10$；

有 $50\%$ 的分数满足 $N\le 300$。

对于全部数据，$2\le N\le 10^5,0\le X_i,Y_i\le 10^9,0\le C_i\le 2$。