第 3 题 Kućice (kuice)

CSP-S 复赛模拟赛 24 · 时间限制 1.0 s · 空间限制 256 MB · 65 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 kuice.in，输出文件 kuice.out。

题目描述

圣诞集市中有 $n$ 个摊位。每个摊位可以抽象为平面直角坐标系中的一个点，其坐标为 $x_i, y_i$。

现在每个摊位均有 50% 的概率违规。所有违规的摊位会被一个栅栏圈住，其中栅栏的形状为所有违规摊位对应的点组成的凸包的边界。当然，一些没有违规的无辜摊位也有可能被圈住。当违规摊位数量小于 3 时，凸包显然会退化为线段、点或空集。

求被圈住摊位的期望数量。可以证明答案可以被表示成 $\frac{m}{2^n}$，其中 $m$ 为正整数。因此只需要输出 $m$ 对 $10^9 + 7$ 取模后的值即可。

输入格式

第一行，一个正整数 $n$，表示摊位的数量。

接下来的 $n$ 行，每行两个整数 $x_i, y_i$，表示摊位的坐标。数据保证不存在坐标相同的摊位且任意三个摊位都不共线。

输出格式

输出 $m$ 对 $10^9 + 7$ 取模后的值。

样例

样例 1

输入：

1
5 5

输出：

1

样例 2

输入：

3
-1 -1
1 -1
0 1

输出：

12

样例 3

输入：

5
0 0
-1 0
2 -1
3 2
0 3

输出：

83

提示

【样例 1 解释】

唯一的摊位违规的概率为 50%，故期望值为 $\frac{1}{2}$。

【样例 2 解释】

违规的情况共有 8 种，而每种情况下被圈住的摊位数分别为 $0, 1, 1, 1, 2, 2, 2, 3$。故期望值为 $\frac{1}{8}(0 + 1 + 1 + 1 + 2 + 2 + 2 + 3) = \frac{12}{8}$。

【数据规模与约定】

本题采用子任务捆绑测试。

• Subtask 1 (10 pts)：每个点都在由所有点组成的凸包的边界上，同时 $n \ge 3$。
• Subtask 2 (30 pts)：除了第一个点外，每个点都在由所有点组成的凸包的边界上，同时 $n \ge 4$，$x_1 = y_1 = 0$。
• Subtask 3 (10 pts)：$1 \le n \le 15$。
• Subtask 4 (30 pts)：$1 \le n \le 100$。
• Subtask 5 (30 pts)：无特殊限制。

对于 100% 的数据，$1 \le n \le 1000$，$|x_i|, |y_i| \le 10^6$。

【提示与说明】

**

**