题目描述

给定平面上的 $n$ 个点，您需要求出每一个点集在凸包上或凸包内的点数之和，注意凸包有可能退化为一条线段，一个点，甚至空集，对 $10^9+7$ 取模的值。

输入格式

第一行为一个整数 $n$。

接下来 $n$ 行，一行两个整数 $x_i,y_i$，表示有一个点是 $(x_i,y_i)$。

输出格式

输出每一个点集被凸包所包含的点数之和，对 $10^9+7$ 取模。

1
5 5

1

不难发现实际上只有一种取法，答案为 $1$。

3
-1 -1
1 -1
0 1

12

有 $8$ 种可能的子集，凸包所包含的点数分别为 $0,1,1,1,2,2,2,3$。

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

83

数据范围与提示

对于全部数据，$1\le n\le 1000$，$|x_i|,|y_i|\le 10^6$，不存在三点共线，不存在重点。