题目描述

Bajtomir 对一组星星很感兴趣。他希望把这些星星划分成两个非空的星座，并要求这种划分能够在平面上自然地画出来。

对于每个星座，可以选择若干对属于该星座的星星，并用直线段连接它们。一个划分是合法的，当且仅当存在一种连线方式满足：

1. 两个星座各自连通，即同一星座中的任意两颗星都能够沿所选择的线段互相到达；
2. 属于不同星座的线段之间不能相交。

Bajtomir 已经知道部分星星属于哪个星座，其余星星尚未确定。你需要计算有多少种补全归属的方法，使最终划分满足上述条件。

由于答案可能很大，输出答案对 $10^9+7$ 取模后的结果。

输入格式

第一行一个整数 $n$，表示星星数量，满足 $3\le n\le 500000$。

接下来 $n$ 行，每行三个整数 $x_i,y_i,c_i$：

• $(x_i,y_i)$ 为第 $i$ 颗星的坐标，$0\le x_i,y_i\le10^9$；
• $c_i\in\{0,1,2\}$；
• 若 $c_i=0$，表示这颗星尚未确定属于哪个星座；
• 若 $c_i=1$ 或 $2$，表示它已经固定属于对应编号的星座。

保证所有星星的坐标两两不同，并且题意要求不存在三颗星共线。

输出格式

输出一个整数，表示合法补全方案数对 $10^9+7$ 取模后的结果。

样例 1

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

2

样例 2

4
0 0 0
100 0 0
100 100 0
0 100 0

12

四个点共有 $16$ 种二染色方式。其中两种把全部点分到同一星座，不满足“两个星座均非空”；另有两种把正方形对角位置分别分为一组，此时两个星座都必须连接一条对角线，两条线段会相交。因此答案为 $16-4=12$。

样例 3

4
0 0 1
3 0 0
1 1 0
0 3 0

7

子任务

原题共 9 个子任务，包含以下典型限制：

• 所有点构成凸多边形并按逆时针顺序给出；
• 所有颜色都已确定；
• 所有颜色都未确定；
• 不出现某一指定颜色；
• 存在四个固定角点 $(0,0),(10^9,0),(10^9,10^9),(0,10^9)$；
• 无附加限制。

完整数据子任务仅占 13 分。