Gadget Construction

Grigory is an engineer who loves developing drones and geometry. He solves most problems himself, but today he faces one that his skills alone cannot solve. You are his best sidekick, and your task is to help him.

There are $n$ cogs on the Cartesian plane. The $i$-th cog is at $(x_i, y_i)$ and has color $c_i$. If $c_i$ is b, the cog is black. If $c_i$ is w, the cog is white. No three cogs lie on the same line.

Grigory chooses a subset $S$ of $4$ or more of the $n$ cogs. He then places a loop of chains around the cogs. The loop satisfies two conditions. Every cog in $S$ either touches the loop or lies inside it. The total length of the chains is minimal.

Consider the cogs in $S$ that touch the loop. Any two cogs that are adjacent on the loop must have different colors, or the gadget does not work. A cog in $S$ that does not touch the loop may have any color.

How many different sets $S$ can Grigory choose to build a properly working gadget? Since the answer can be very large, print it modulo $10^9+7$.

The first line contains an integer $n$. Each of the next $n$ lines contains two integers $x_i$, $y_i$ and a character $c_i$, which give the coordinates and color of the $i$-th cog.

Print the number of valid sets $S$ modulo $10^9+7$.

$4 \le n \le 500$. For every $i$, $-10^8 \le x_i, y_i \le 10^8$, and $c_i$ is b or w. For $i \ne j$, $(x_i, y_i) \ne (x_j, y_j)$. No three cogs lie on the same line.