톱니바퀴 장치 구성

그리고리는 드론과 기하학 개발을 좋아하는 엔지니어다. 대부분의 문제는 혼자 풀지만, 오늘은 그의 능력만으로는 풀 수 없는 문제를 마주했다. 당신은 그의 가장 든든한 조력자로서 그를 도와야 한다.

직교 좌표평면 위에 톱니바퀴 $n$개가 있다. $i$번째 톱니바퀴는 $(x_i, y_i)$에 있고 색 $c_i$를 가진다. $c_i$가 b이면 검은색, w이면 흰색이다. 세 톱니바퀴가 한 직선 위에 놓이는 경우는 없다.

그리고리는 톱니바퀴 $4$개 이상으로 이루어진 부분집합 $S$를 고른다. 그다음 톱니바퀴 둘레에 사슬로 된 고리를 둔다. 이 고리는 두 조건을 만족한다. $S$의 모든 톱니바퀴는 고리에 닿거나 고리 안쪽에 있다. 사슬의 총 길이는 최소이다.

고리에 닿은 $S$의 톱니바퀴를 살펴보자. 고리 위에서 서로 인접한 두 톱니바퀴는 색이 달라야 한다. 그렇지 않으면 장치가 제대로 작동하지 않는다. 고리에 닿지 않은 $S$의 톱니바퀴는 색이 무엇이든 상관없다.

그리고리가 제대로 작동하는 장치를 만들 수 있는 서로 다른 집합 $S$의 개수는 몇 개인가? 답이 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 구하라.

첫 줄에 정수 $n$이 주어진다. 이어지는 $n$개의 줄에는 정수 $x_i$, $y_i$와 문자 $c_i$가 주어지며, 이는 $i$번째 톱니바퀴의 좌표와 색이다.

조건을 만족하는 집합 $S$의 개수를 $10^9+7$로 나눈 나머지로 출력한다.

$4 \le n \le 500$이다. 모든 $i$에 대해 $-10^8 \le x_i, y_i \le 10^8$이고, $c_i$는 b 또는 w이다. $i \ne j$이면 $(x_i, y_i) \ne (x_j, y_j)$이다. 세 톱니바퀴가 한 직선 위에 있는 경우는 없다.