Description

Farmer John wants to build a triangular pasture for his cows.

There are $N$ ($3 \leq N \leq 10^5$) fence posts located at distinct points $(X_1, Y_1) \ldots (X_N, Y_N)$ on the 2D plane of the farm. He may choose any three points to form a triangular pasture, as long as one side of the triangle is parallel to the $x$-axis and another side is parallel to the $y$-axis.

What is the sum of the areas of all possible pastures that FJ can form?

Input Format

The first line contains $N$.

The next $N$ lines each contain two integers $X_i$ and $Y_i$, both in the range $-10^4 \ldots 10^4$, describing the position of a fence post.

Output Format

Since the sum of areas may not be an integer and may be very large, output the remainder of twice the sum of areas modulo $10^9 + 7$.

4
0 0
0 1
1 0
1 2

3

Hint

Sample Explanation:

The fence posts $(0,0)$, $(1,0)$, and $(1,2)$ form a triangle with area $1$, and the fence posts $(0,0)$, $(1,0)$, and $(0,1)$ form a triangle with area $0.5$. Therefore, the answer is $2 \times (1 + 0.5) = 3$.

Subtasks:

• Test case $2$ satisfies $N = 200$.
• Test cases $3$-$4$ satisfy $N \leq 5000$.
• Test cases $5$-$10$ have no additional constraints.

Translated by ChatGPT 5