Under construction

Still being built. Things may change

Inverted Triangles

Interview

Time limit2sMemory limit1024 MB

Summary
Given N points, find the sum of doubled areas of all inverted triangles, where the middle-x point has the lowest y, modulo 1000000007.
Level

Medium6 of 10

Topics
Sorting, Prefix sum, Geometry
Solved
No attempts yet

Problem

On an infinite two-dimensional coordinate plane, there are NN points. The points are numbered from 11 to NN, and the coordinates of point ii are (xi,yi)(x_i, y_i). All point coordinates are distinct.

Choose three distinct numbers aa, bb, and cc between 11 and NN inclusive. Connecting the points for these numbers with line segments forms a triangle. A triangle that satisfies all of the following conditions is called an inverted triangle.

  • xa<xb<xcx_a < x_b < x_c.
  • yb<yay_b < y_a.
  • yb<ycy_b < y_c.

Let SS be the sum of the areas of all inverted triangles that can be formed by choosing three points. Print the remainder when 2S2S is divided by 1,000,000,0071,000,000,007 (= 109+710^9 + 7). It can be proven that 2S2S is always an integer.

Input

The first line contains NN. (3≤N≤300 0003 \le N \le 300\,000)

Each of the next NN lines contains two integers xix_i and yiy_i, separated by a space. (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9)

Output

Print the remainder when 2S2S is divided by 1,000,000,0071,000,000,007. This number is prime.

Examples2

  1. Example 1

    Input
    6
    4 -5
    -7 15
    6 8
    -3 3
    0 12
    2 -7
    
    Expected output
    1154
    
  2. Example 2

    Input
    3
    -1 -1
    0 0
    1 1
    
    Expected output
    0