JOI 2016/2017 spring camp- 항구 > 문제은행 : 정보올림피아드&알고리즘



4950 : 항구

제한시간
5000 ms   
메모리제한
1024 MB   
해결횟수
3 회   
시도횟수
9 회   

문제

당신은 항구의 관리자이다. 항구에는 매일 많은 양의 화물이 들어오고 나간다.

오늘은 N개의 화물이 항구를 거쳐갈 예정이다.

항구에는 화물을 쌓을 수 있는 A와 B의 두 공간이 있다.

당신은 화물이 들어오면 두 공간 중 한 공간의 위로 화물을 쌓아야 하고, 화물이 나가야 할 시간에는 그 화물이 맨 위에 있도록 해야한다.

N개의 화물이 항구에 들어오는 시간과 나가야 하는 시간이 주어지면 모든 화물을 조건에 맞게 운반할 수 있는 공간 배정 방법의 수를 구하라.

두 방법이 다르다는 것은 두 방법에서 A와 B중 서로 다른 곳에 배정된 컨테이너가 존재한다는 의미이다.


입력형식

첫 줄에 화물의 개수 N이 주어진다. (1 <= N <= 1 000 000)

이후 N줄에 거쳐 각 화물이 들어오는 시간 S_i, 나가는 시간 T_i가 주어진다.

(1 <= S_i < T_i <= 2N, S_i와 T_i로 주어지는 모든 시간은 서로 다르다.)


출력형식

조건에 맞게 화물을 공간에 배정하는 방법의 수를 10억 7로 나눈 나머지를 출력하라.


입력 예

4
1 3
2 5
4 8
6 7

출력 예

4

입력 예

3
1 4
2 5
3 6

출력 예

0


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP