题目描述

平面上に $N$ 個の点 $P_1,\ P_2,\ \dots,\ P_N$ があり、$P_i$ の座標は $(X_i,\ Y_i)$ です。どの $3$ 点も同一直線上にないことが分かっています。

要素数が $3$ 以上であるような $\{\ 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)$ で割ったあまりを求めることに注意すること。

题目大意

hhoppitree 给了你平面直角坐标系中的 $n$ 个点，保证无三点共线，现在他想要从中选出至少三个点，使得这个点集所构成的凸包的面积为整数，求有多少种方案。

4
0 0
1 2
0 1
1 0

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

4060436

提示

制約

• $3\ \leq\ N\ \leq\ 80$
• $0\ \leq\ |X_i|,\ |Y_i|\ \leq\ 10^4$
• どの $3$ 点も同一直線上にない。
• 入力は全て整数である。

Sample Explanation 1

$ \{\ P_1,\ P_2,\ P_4\ \},\ \{\ P_2,\ P_3,\ P_4\ \} $ が条件を満たします。