문제
당신은 항구의 관리자이다. 항구에는 매일 많은 양의 화물이 들어오고 나간다.
오늘은 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로 나눈 나머지를 출력하라.
예제 #1
4
1 3
2 5
4 8
6 7
4
예제 #2
3
1 4
2 5
3 6
0
출처
JOI 2016/2017 spring camp
로그인해야 코드를 작성할 수 있어요.