Eureka

Zhang 교수는 평면 위에 $n$개의 점을 찍었고, 점에는 $1, 2, \ldots, n$ 번호가 붙어 있다. $i$번 점의 좌표는 $(x_i, y_i)$이다. Zhang 교수는 최고 집합의 개수를 알고 싶어 한다. 개수는 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다.

점 번호들의 집합 $P$에 최고 쌍이 하나 이상 있으면, $P$를 최고 집합이라 한다. 서로 다른 두 번호 $u$, $v$ ($u, v \in P$, $u \ne v$)가 최고 쌍이라는 것은 $P$의 모든 $w$에 대해 $f(u, v) \ge g(u, v, w)$가 성립한다는 뜻이다. 여기서 $f(u, v) = \sqrt{(x_u - x_v)^2 + (y_u - y_v)^2}$이고, $g(u, v, w) = \frac{f(u, v) + f(v, w) + f(w, u)}{2}$이다.

여러 개의 테스트 케이스가 주어진다. 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 점의 개수 $n$ ($1 \le n \le 1000$)이 주어지고, 이어서 $n$개의 줄에 정수 $x_i$와 $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)가 한 줄에 하나씩 주어진다. 테스트 케이스는 250개를 넘지 않으며, 모든 테스트 케이스의 $n$을 합친 값은 $40\,000$ 이하이다.

각 테스트 케이스마다 최고 집합의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.