Farmer John wants to create a triangular pasture for his cows.
There are N fence posts in total (3 ≤ N ≤ 100) as distinct (X
1,Y
1)…(X
N, Y
N) points on the farm map. He can choose three of them to form the vertices of a triangular pasture, but so that one of the sides is parallel to the x-axis and the other is parallel to the y-axis.
What is the sum of the areas of all possible pastures that a FD can form?
Input
The first line contains N.
Each of the following N lines contains two integers Xi and Yi, each in the interval −10
4…10
4 inclusive, describing the position of the post.
Imprint
Since the sum of areas may not be an integer and very large, print the remainder after dividing twice the sum of areas by 10
9+7.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4
0 0
0 1
10
1 2
|
3 |
Points (0,0), (1,0), (1,2) form a triangle with area 1.
Points (0,0), (1,0), (0,1) form a triangle with area 0.5.
So the answer is 2⋅(1+0.5)=3. |