Fence Invasion

Time limit5sMemory limit512 MB

Summary

Count how many distinct convex polygons can be formed as the convex hull of some subset of at least 3 of the given points, modulo 1e9+7.

Level: Hard8 of 10
Topics: Geometry, Combinatorics, Dynamic programming, Sorting
Solved: No attempts yet

Problem

A coder at one science high school is known for his algorithms. He turns an $O(N^3)$ algorithm into an $O(N^2)$ one, and he solves hard problems the moment he reads them.

Only the programming club at a neighboring science high school refused to admit that. When the coder heard about it, he marched over to show what he can do and took their surrender without trouble. That was still not enough for him, so he decided to ring the school with a fence engraved with his handle.

There are $N$ spots around the school where a post can be driven. The coder picks at least 3 of these spots, drives a post at each chosen spot, and builds the fence along the convex hull of the posts. He has plenty of money and plenty of time, so he plans to build every fence shape he can, one per day.

Count how many different fence shapes there are. Two fences have the same shape when they cover the same region of the plane.

Input

The first line contains the number of spots $N$ ( $3 \le N \le 300$ ) where a post can be driven.

Each of the next $N$ lines contains the integer coordinates $x_i$ and $y_i$ of one spot, separated by a space. ( $|x_i|, |y_i| \le 10^9$ )

No three spots lie on one line.

Output

Print the number of different fence shapes modulo $10^9+7$ on the first line.

Examples2

Example 1
Input
```
4
1 1
1 2
2 1
2 2
```
Expected output
```
5
```
Example 2
Input
```
3
0 0
5 1
2 7
```
Expected output
```
1
```