역삼각형

아직 제출이 없습니다시간 제한2초메모리 제한1024 MB

문제

무한한 크기의 2차원 좌표평면 위에 $N$개의 점이 있다. 점은 $1$번부터 $N$번까지 번호가 붙어 있고, $i$번 점의 좌표는 $(x_i,y_i)$이다. 모든 점의 좌표는 서로 다르다.

$1$ 이상 $N$ 이하의 서로 다른 세 개의 번호 $a$, $b$, $c$를 고른 뒤, 각 번호에 해당하는 점과 점 사이를 선분으로 이으면 삼각형을 만들 수 있다. 이때, 아래 조건을 모두 만족하는 삼각형을 역삼각형이라고 한다.

  • $x_a<x_b<x_c$.
  • $y_b<y_a$.
  • $y_b<y_c$.

세 점을 선택해서 만들 수 있는 모든 역삼각형 넓이의 합을 $S$라고 했을 때, $2S$를 $1\,000\,000\,007(= 10^9 + 7)$로 나눈 나머지를 출력하라. $2S$는 항상 정수임을 증명할 수 있다.

입력

첫째 줄에 $N$이 주어진다. $(3 \le N \le 300\ 000)$

다음 $N$개의 줄에 두 정수 $x_i$, $y_i$가 공백으로 구분되어 주어진다. $(-10^9 \le x_i, y_i \le 10^9)$

출력

$2S$를 $1\,000\,000\,007(= 10^9 + 7)$로 나눈 나머지를 출력한다. 이 수는 소수이다.