Problem Description

There are $N$ bus stops on a 2D plane, and the coordinates of the $i$-th bus stop are $(x_i, y_i)$. Here, $x_i$ and $y_i$ are both integers.

Snuke wants to know the sum of the areas of the convex hulls (the smallest convex polygon that can enclose all the selected points) for all possible selections of at least 3 bus stops out of the $N$ bus stops. You have been tasked to calculate this value for Snuke.

It can be proven that if this total area is expressed as $a/2$, $a$ is always an integer. Therefore, please output $a$ modulo $10^9+7$.

Input Format

The input is given from the standard input in the following format:

$N$ $x_1$ $y_1$ : $x_N$ $y_N$

Output Format

Output the sum of the areas multiplied by 2, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

4
0 0
1 0
-1 1
-1 -1

Sample Output #1

12

Sample Input #2

10
-3 1
2 3
-2 0
-3 2
-5 -5
1 -5
2 4
5 4
5 -3
-2 5

Sample Output #2

75282

Notes/Hints

Constraints

• $3 \leq N \leq 2000$
• $|x_i|, |y_i| \leq 10000$
• $(x_i, y_i) \neq (x_j, y_j)$ $(1 \leq i < j \leq N)$
• No three given points are collinear
• All values given in the input are integers

Sample Explanation 1

• When selecting the 1st, 2nd, and 3rd points, the area of the convex hull is $1/2$.
• When selecting the 1st, 2nd, and 4th points, the area of the convex hull is $1/2$.
• When selecting the 1st, 3rd, and 4th points, the area of the convex hull is $1$.
• When selecting the 2nd, 3rd, and 4th points, the area of the convex hull is $2$.
• When selecting the 1st, 2nd, 3rd, and 4th points, the area of the convex hull is $2$.

Thus, the total area is $1/2 + 1/2 + 1 + 2 + 2 = 6$. Output $12$, which is the total area multiplied by 2, modulo $10^9+7$.

见题面 Input 部分

见题面 Output 部分