Under construction

Still being built. Things may change

Triangles (Silver)

Interview

Time limit1sMemory limit512 MB

Summary
Given N points, sum twice the areas of all right triangles whose legs are parallel to the axes, modulo 1e9+7.
Level

Medium6 of 10

Topics
Math, Geometry, Combinatorics, Hash map
Solved
No attempts yet

Problem

Farmer John would like to create a triangular pasture for his cows.

There are NN fence posts (3≤N≤1053\le N\le 10^5) at distinct points (X1,Y1)…(XN,YN)(X_1, Y_1) \ldots (X_N, Y_N) on the 2D map of his farm. He can choose three of them to form the vertices of the triangular pasture as long as one of the sides of the triangle is parallel to the xx-axis and another side is parallel to the yy-axis.

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

Input

The first line contains NN.

Each of the next NN lines contains two integers XiX_i and YiY_i, each in the range −104…104-10^4 \ldots 10^4 inclusive, describing the location of a fence post.

Output

As the sum of areas is not necessarily an integer and may be very large, output the remainder when two times the sum of areas is taken modulo 109+710^9+7.

Hint

Fence posts (0,0)(0,0), (1,0)(1,0), and (1,2)(1,2) give a triangle of area 11, while (0,0)(0,0), (1,0)(1,0), and (0,1)(0,1) give a triangle of area 0.50.5. Thus, the answer is 2⋅(1+0.5)=32\cdot (1+0.5)=3.

Examples1

  1. Example 1

    Input
    4
    0 0
    0 1
    1 0
    1 2
    
    Expected output
    3