JOI 君是一个热爱观察星空的少年。他几乎每晚都会观察星空，并乐于研究每一颗星星属于哪个星座。

一天晚上，JOI 君像往常一样观察星空时，发现了 $N$ 颗从未见过的星星。JOI 君对这些星星所属的星座产生了兴趣，于是他拍下了夜空的照片，并在第二天去图书馆查阅了相关资料。结果发现，这些星星全部属于星座 A 或星座 B 中的某一个，并且他已经知道了其中一些星星所属的星座。然而，对于其余的星星，他并不知道它们属于哪个星座。JOI 君想知道，星座 A 和星座 B 所包含的星星集合共有多少种可能的组合。注意，星星的大小足够小，可以视为点。

在此，星座定义为由照片上的 1 个或多个星星以及连接星星的若干线段组成，并满足以下条件。请注意，仅由 1 颗星星组成的集合也被视为一个星座。

• 构成同一个星座的任意两颗星星，都可以通过沿着该星座的线段相互到达。
• 构成一个星座的线段与构成另一个星座的线段不相交。

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

• 任意 3 颗星星都不在照片上的同一直线上。
• 每一颗星星都属于星座 A 或星座 B，且不存在除 JOI 君发现的星星以外属于星座 A 或星座 B 的星星。

题目描述

给定 $N$ 颗星星的信息，请编写一个程序，计算星座 A 和星座 B 所包含的星星集合的可能总数，并将结果对 $1\,000\,000\,007$ ($= 10^9 + 7$) 取模。

数据范围

• $2 \le N \le 100\,000$：JOI 君发现的星星数量
• $0 \le X_i \le 10^9, 0 \le Y_i \le 10^9$：星星 $i$ 在照片上的坐标

输入格式

从标准输入读取以下内容：

• 第 1 行包含一个整数 $N$，表示 JOI 君发现的星星数量。
• 接下来的 $N$ 行包含星星的信息。第 $i+1$ 行 ($1 \le i \le 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$) 取模后的结果。如果不存在这样的集合，则输出 0。

子任务

• 对于配分 10% 的测试数据，满足 $N \le 10$。
• 对于配分 50% 的测试数据，满足 $N \le 300$。

样例

样例输入 1

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

样例输出 1

2

说明

该输入样例对应下图。其中，黑点表示属于星座 A 的星星，白点表示属于星座 B 的星星，× 号表示不知道属于哪个星座的星星。

该输入的答案为 2 种情况，即星星 3 属于星座 A 的情况和星星 3 属于星座 B 的情况。每种情况的星座示意图如下所示。请注意，当星星 3 属于星座 A 时，星座 A 的连线方式可能有多种，但所有这些方式应合并计为 1 种情况。

星 3 属于星座 A 的情况 | 星 3 属于星座 B 的情况