Grigory 是一位富有才华的工程师，他热爱开发无人机，当然也热爱几何。作为一名出色的问题解决者，他总能在困难的情况下想出解决方案，但今天，他遇到了一个仅凭个人能力无法解决的问题。因此，作为他最好的助手，你的任务是帮助他。

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

Grigory 想要用其中一些齿轮制作一个装置。为此，他首先选择 $n$ 个齿轮中的一个子集 $S$，该子集包含至少 $4$ 个齿轮。然后，在这些齿轮周围放置一圈链条。选择的链条回路满足以下条件：

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

例如，下图展示了为选定的一组齿轮放置链条的情况。

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

Grigory 可以选择多少种不同的集合 $S$ 来构建一个正常工作的装置？由于答案可能非常大，请输出其模 $10^9 + 7$ 的值。

输入格式

第一行包含一个整数 $n$。

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

输出格式

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

数据范围

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

样例

输入样例 1

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

输出样例 1

1

输入样例 2

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

输出样例 2

9

输入样例 3

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

输出样例 3

0