整数凸包

题目描述

平面上有 $N$ 个点 $P_1, P_2, \dots, P_N$。$P_i$ 的坐标为 $(X_i, Y_i)$。已知任意三点不共线。

对于 $\{ P_1, P_2, \dots, P_N \}$ 中至少包含三个元素的子集 $S$，定义 $S$ 的凸包如下：

凸包是面积最小的凸多边形，使得 $S$ 的所有点都在该多边形内部或边上。

求凸包面积为整数的子集 $S$ 的个数，并对 $(10^9 + 7)$ 取模。

输入格式

输入按以下格式从标准输入给出：

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

输出格式

输出答案。注意要求的是对 $(10^9 + 7)$ 取模后的结果。

样例

4
0 0
1 2
0 1
1 0

2

$\{ P_1, P_2, P_4 \}$ 和 $\{ P_2, P_3, P_4 \}$ 满足条件。

23
-5255 7890
5823 7526
5485 -113
7302 5708
9149 2722
4904 -3918
8566 -3267
-3759 2474
-7286 -1043
-1230 1780
3377 -7044
-2596 -6003
5813 -9452
-9889 -7423
2377 1811
5351 4551
-1354 -9611
4244 1958
8864 -9889
507 -8923
6948 -5016
-6139 2769
4103 9241

4060436

数据范围

• $3 \le N \le 80$
• $0 \le |X_i|, |Y_i| \le 10^4$
• 任意三点不共线
• 输入均为整数