题目描述

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

对于至少包含三个元素的子集 $S$，我们定义 $S$ 的 凸包 如下：

• 凸包是面积最小的凸多边形，使得 $S$ 中的每个点都在该多边形内部或边界上。

找出满足凸包面积为整数的子集 $S$ 的数量，模 $(10^9 + 7)$。

约束条件

• $3 \\leq N \\leq 80$
• $0 \\leq |X_i|, |Y_i| \\leq 10^4$
• 不存在三个点共线。
• 输入中的所有值都是整数。

输入

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

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

输出

打印答案。请注意，要求你输出答案模 $(10^9 + 7)$ 的结果。

示例输入1

4
0 0
1 2
0 1
1 0

示例输出1

2

满足条件的子集有 $\\{ P_1, P_2, P_4 \\}$ 和 $\\{ P_2, P_3, P_4 \\}$。

示例输入2

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

示例输出2

4060436