题目描述

格里戈里是一位才华横溢的工程师，热爱开发无人机，当然也热爱几何。作为一名技艺高超的问题解决者，他能在困境中想出解决方案，但今天他遇到了一个仅凭自己能力无法解决的问题。因此，作为他最得力的搭档，你的任务就是帮助他。

平面上有 $n$ 个齿轮。第 $i$ 个齿轮位于坐标 $(x_i, y_i)$，并有一个字符 $c_i$ 描述其颜色——“b”表示黑色齿轮，“w”表示白色齿轮。此外，没有三个齿轮共线。

格里戈里想用其中一些齿轮搭建一个装置。为此，他首先选择一个由 $n$ 个齿轮中的 $4$ 个或更多齿轮组成的子集 $S$。然后，一条链条环会放置在齿轮周围。链条环的选择满足：

• $S$ 中的每个齿轮要么接触链条环，要么位于其内部。
• 链条的总长度最小。

例如，下图展示了为某个选定齿轮集合所放置的链条。

:::align{center} :::

最后，考虑 $S$ 中接触链条环的齿轮。这些是最重要的齿轮，因此它们之间不能相互干扰。因此，链条环上任意两个相邻的齿轮必须具有不同的颜色，否则制成的装置将无法正常工作。如果 $S$ 中的齿轮不接触链条环，则其颜色可以任意。

格里戈里可以选择多少个不同的集合 $S$ 来建造一个正常工作的装置？由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $n$。接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ 和一个字符 $c_i$，表示第 $i$ 个齿轮的坐标和颜色。

输出格式

输出满足条件的集合 $S$ 的数量对 $10^9 + 7$ 取模的结果。

4
0 0 w
1 0 b
1 1 w
0 1 b

1

6
0 0 w
0 4 b
1 2 w
3 2 b
4 0 b
4 4 w

9

4
0 0 b
1 0 w
1 1 w
0 1 b

0

提示

• $4 \le n \le 500$
• $-10^8 \le x_i, y_i \le 10^8$，对于 $i = 1, 2, \dots, n$
• $c_i \in \{\texttt{b}, \texttt{w}\}$，对于 $i = 1, 2, \dots, n$
• $(x_i, y_i) \ne (x_j, y_j)$，对于 $i \ne j$
• 没有三个齿轮共线。

翻译由 DeepSeek V3.2 完成