쿠치체

자그레브 크리스마스 마켓의 모든 두 번째 부스는 사실 뒷거래로 세워졌다는 것은 누구나 알고 있다. 올해 당국은 불법으로 세워진 부스를 처벌하기 위해 점검관을 파견하기로 했다.

$n$개의 부스가 있으며, 이들은 평면 위의 점으로 나타낼 수 있고, 그중 어느 세 점도 같은 직선 위에 있지 않다. 당국은 부패로 운영되는 부스를 찾아내어 마을의 나머지 부분과 울타리로 분리할 것이다. 울타리는 해당 부스들을 둘러싸며, 그들을 모두 포함하는 가장 작은 볼록 다각형의 모양을 이룰 것이다. 즉, 울타리는 선택된 점 집합의 볼록 껍질의 경계라고 생각할 수 있다. 안타깝게도, 일부 무고한 부스도 함께 울타리 안에 갇힐 수 있다.

현장 점검 전에 당국은 각 부스가 부패했을 확률을 50%로 추정한다. 이를 염두에 두고, 그들은 결국 울타리 안에 갇히게 될 부스 수의 기댓값이 얼마인지 궁금해한다. 기댓값은 특정 부스 부분집합이 선택될 확률에 그 선택에서 울타리 안에 갇히는 부스 수를 곱한 값을, 가능한 모든 부분집합 선택에 대해 더한 값으로 정의된다. 물론, 선택된 부분집합이 세 점 미만으로 이루어지면 볼록 껍질은 퇴화하여 선분, 점 또는 공집합이 된다.

원하는 기댓값은 어떤 양의 정수 $m$에 대해 $\frac{m}{2^n}$ 꼴로 쓸 수 있음이 증명된다. 당국은 기댓값을 알고 싶어 하므로, 친절하게도 $m$의 값을 계산해 달라고 요청한다. 답이 매우 클 수 있으므로, $10^9 + 7$로 나눈 나머지를 출력해야 한다.

첫 번째 줄에는 양의 정수 $n$ ($1 ≤ n ≤ 1000$)이 주어지며, 이는 부스의 수이다.

다음 $n$개의 줄 중 $i$번째 줄에는 두 양의 정수 $x_i$, $y_i$ ($|x_i|, |y_i| ≤ 10^6$)가 주어지며, 이는 각각 $i$번째 부스의 $x$ 좌표와 $y$ 좌표이다. 두 부스가 같은 위치에 있는 경우는 없다.

어느 세 부스도 같은 직선 위에 있지 않다.

단일 줄에 위에서 설명한 수 $m$을 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 번째 예제의 해설: 첫 번째이자 유일한 부스가 울타리 안에 갇힐 확률은 50%이므로, 기댓값은 $\frac{1}{2}$이다.

두 번째 예제의 해설: 부분집합에 대해 여덟 가지 선택이 가능하고, 그 선택들에 대해 울타리 안에 갇히는 부스 수는 0, 1, 1, 1, 2, 2, 2, 3이다. 그러면 기댓값은 $\frac{1}{8}(0 + 1 + 1 + 1 + 2 + 2 + 2 + 3) = \frac{12}{8}$이다.