여우가 정보섬에 올라온 이유

면접 대비

시간 제한1초메모리 제한256 MB

요약

별 세 개 (s,t,u)가 s.x < t.x < u.x이고 s.y > t.y < u.y를 만족할 때 V자 별자리라 하고, 그 개수를 10^9+7로 나눈 나머지를 구한다.

난이도: 보통10점 중 6점
유형: 정렬, 이분 탐색, 누적 합, 조합론
정답자: 아직 제출이 없습니다

문제

여우가 정보섬에 올라왔다!

오늘도 하늘에는 아름다운 별들이 빛나고 있다. 정보섬은 언덕 꼭대기에 있기 때문에 별이 잘 보이기로 유명하다. 그래서인지 여우 한 마리가 정보섬에 올라와 밤하늘을 바라보며 별자리를 만들고 있다. 여우는 세 개의 별을 연결해 V형 별자리를 만드는데, V가 자신의 얼굴과 닮았기 때문이라나 뭐라나. 여우는 자신의 시점을 기준으로 생각하기 때문에 V가 회전한 모양(<, >, ㄴ, ㄱ, ^ 등)은 V라고 생각하지 않는다.

여우는 만들 수 있는 V형 별자리의 총 개수가 궁금해졌다. 그런데 일일이 세보기에는 별이 너무 많아서, 여우는 뛰어난 프로그래머인 당신에게 도움을 요청했다! 귀여운 여우를 위해 얼마나 많은 V형 별자리가 만들어질 수 있는지 계산해 주자.

V형 별자리를 명확하게 정의하면 다음과 같다. 세 별 (s,t,u)가 s.x < t.x < u.x이고 s.y > t.y < u.y이면 V형 별자리이다. 예를 들어 아래 '정보섬의 밤하늘 참고도'에서 (a,b,c)는 V형 별자리를 이루지만 (d,b,c)는 d.x < b.x가 아니므로 V형 별자리가 아니다. V형 별자리의 개수를 셀 때, 한 별이 여러 별자리에 속할 수 있다.

답이 매우 커질 수 있으므로 $(10^9+7)$ 로 나눈 나머지를 출력한다.

입력

첫 줄에 별의 개수 $N$ 이 주어진다. 그 다음 줄부터 $N$ 개의 줄에 걸쳐 별의 좌표 $x$ $y$ 가 주어진다.

출력

(만들 수 있는 V형 별자리의 개수) mod $(10^9+7)$ 을 출력한다.

제한

$1 \le N \le 2\times 10^5$
$-2\times 10^5 \le x,y \le 2\times 10^5$ ( $x,y$ 는 정수)

예제2

예제 1
입력
```
4
-1 1
0 0
1 1
0 1
```
예상 출력
```
1
```

예제 2

입력

예상 출력