초고속철도

최고 속력 600 km/h로 달리는 초고속철도 시험선로가 직선 위에 놓여 있다. 선로의 여러 구간을 검사하기 위해 로봇들이 설치되어 있으며, 각 로봇은 하나의 연속된 검사구간을 맡는다. 두 로봇의 검사구간이 서로 겹치면 두 로봇 사이에는 많은 데이터를 주고받아야 하므로, 그 둘 중 적어도 하나에는 특별한 데이터 처리장치를 부착해야 한다.

아래 그림처럼 네 로봇 a, b, c, d가 있다고 하자. a와 b의 검사구간은 겹치므로 둘 중 하나 이상에 처리장치가 필요하다. b와 c, b와 d, c와 d도 같은 조건을 만족해야 한다.

이 조건을 만족하는 부착 방법은 여러 가지가 있을 수 있다. 위 그림에서는 네 로봇 모두에 부착할 수도 있고, b와 c에만 부착할 수도 있다. 조건을 만족하는 모든 부착 방법은 {a, b, c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {b, d}, {b, c}의 일곱 가지이다.

로봇들의 검사구간이 주어졌을 때, 모든 겹치는 로봇 쌍에 대해 적어도 한쪽에 처리장치를 부착하는 방법의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 로봇의 개수 N이 주어진다. (1 <= N <= 100,000)

둘째 줄부터 N개의 줄에는 각 로봇이 맡은 검사구간의 왼쪽 끝점 좌표와 오른쪽 끝점 좌표가 공백으로 구분되어 주어진다.

모든 좌표는 0 이상 10,000,000 이하의 정수이다. 각 구간의 왼쪽 끝점은 오른쪽 끝점보다 작다. 또한 모든 구간 끝점의 좌표는 서로 다르다.

조건을 만족하는 처리장치 부착 방법의 수를 출력한다.

방법의 수가 20,070,713 이상이면 20,070,713으로 나눈 나머지를 출력한다. 계산 도중 오버플로우가 발생할 수 있음에 유의한다.