31006번 - 역삼각형

문제

무한한 크기의 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$라고 했을 때, 2ドルS$를 1ドル,000円,000円,007円(= 10^9 + 7)$로 나눈 나머지를 출력하라. 2ドルS$는 항상 정수임을 증명할 수 있다.

입력

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

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

출력

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

제한

힌트