Eureka

Professor Zhang draws $n$ points on the plane, labeled $1, 2, \ldots, n$. The $i$-th point is at $(x_i, y_i)$. Professor Zhang wants to count the best sets modulo $10^9 + 7$.

A set $P$ of point labels is a best set if and only if $P$ contains at least one best pair. Two distinct labels $u$ and $v$ ($u, v \in P$, $u \ne v$) form a best pair if, for every $w \in P$, $f(u, v) \ge g(u, v, w)$, where $f(u, v) = \sqrt{(x_u - x_v)^2 + (y_u - y_v)^2}$ and $g(u, v, w) = \frac{f(u, v) + f(v, w) + f(w, u)}{2}$.

There are multiple test cases. The first line contains an integer $T$, the number of test cases. Each test case begins with an integer $n$ ($1 \le n \le 1000$), the number of points, followed by $n$ lines that each contain two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$). There are no more than $250$ test cases, and the sum of $n$ over all test cases is at most $40\,000$.

For each test case, print the number of best sets modulo $10^9 + 7$ on its own line.