초고속철도

최고 속력 600 km/h로 운행하는 것을 목표로 하는 ‘한국형 초고속철도 사업’이 순조롭게 진행되고 있다. 이미 초고속철도의 시험선로를 구축하였고 열차를 시험운행하고 있다. 그리고 선로의 상태를 검사하기 위하여, 선로의 지정된 검사구간을 담당하는 로봇을 설치하였다. 그런데 검사구간이 서로 겹치는 로봇 사이에는 빈번한 데이터 교환이 필요하다. 따라서 이를 지원할 데이터 송수신 장치를 모든 로봇에 설치할 뿐만 아니라, 특별한 데이터 처리장치를 로봇에 부착하기로 하였다. 그러나 이 처리장치는 모든 로봇에 부착하지 않아도 되지만, 두 로봇이 담당하고 있는 검사구간이 서로 겹치면 이 두 로봇 중에서 적어도 하나에는 반드시 부착되어야 한다.

아래 그림과 같은 시험선로에서 네 개의 로봇 \(a\), \(b\), \(c\), \(d\)가 있고, 각 로봇의 검사구간은 아래와 같다고 하자. 로봇 \(a\)와 \(b\)는 담당하는 선로의 검사구간이 겹치므로 둘 중 최소한 하나에 처리장치가 부착되어야 한다. 로봇 \(b\)와 \(c\), \(b\)와 \(d\), 그리고 \(c\)와 \(d\)의 경우도 마찬가지이다.

위의 조건을 만족하면서 처리장치를 부착하는 것은 여러 가지 경우가 있을 수 있다. 위 그림의 예에서 {\(a\), \(b\), \(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 \le N \le 100{,}000)\)이 입력된다. 둘째 줄부터 \(N\) 개의 줄에 한 줄에 하나씩 로봇이 담당하는 검사구간의 왼쪽 끝점의 좌표와 오른쪽 끝점의 좌표가 빈 칸을 사이에 두고 주어진다. 이들 좌표는 모두 0 이상 10,000,000 이하인 정수이다. 각 검사구간의 왼쪽 끝점의 좌표가 오른쪽 끝점의 좌표보다 항상 작다. 또한 검사구간들의 끝점들의 좌표는 모두 서로 다르다. 다시 말하면, 어떤 좌표 값에도 두 개 이상의 검사구간의 끝점이 위치하지 않는다.

첫째 줄에 문제의 조건을 만족하면서 처리장치를 부착할 수 있는 경우의 수를 출력한다. 만약 경우의 수가 20,070,713 이상일 때에는 20,070,713으로 나눈 나머지를 출력한다. 또한 계산 도중 오버플로우가 발생할 수 있음을 유의하라.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2007 > 2차 대회 > 고등부 2번