Informatica Online Judge

  항만 작업(Tiny) [1906 / 0772]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 9   Total Tried : 16


The Champion of this Problem (C++) : gs17067 - 0ms / 492byte
My Best Submission (C++) : N/A

[JOI Spring Training Camp Day1]

Background

GS항구에는 매일 많은 콘테이너가 배를 통해서 들어온다.

이 콘테이너들은 트레일러에 의해 매일 전국 각지로 배송된다.

배로 들어온 콘테이너들을 트레일러로 운송하기 전에 항만에서 보관해야한다.

항만에 콘테이너를 보관할 수 있는 보관소는 2곳뿐이다.

이 2곳의 보관소는 스택의 형태로 공간상 하나의 콘테이너만 놓을 수 있다.

하지만 위로는 한계 없이 계속 쌓아 놓을 수 있다.

단 쌓은 콘테이너는 가장 위에 올라가게 되며, 트레일러에 탑재할 때에도 가장 위의 콘테이너만 운반할 수 있다.

경곽이는 오늘 GS항만에 들어오는 콘테이너들을 보관하는 업무를 맡았다.

경곽이는 n개의 콘테이너를 입항하는 시간과 출항하는 시간이 주어질 때, 보관소에 콘테이너를 보관할 수 있는 방법의 경우의 수를 구하는 프로그램을 작성하시오.

(단, 수가 너무 커질 수 있기 때문에 10억 7로 나눈 나머지를 구해야 한다.)

Input

첫 번재 줄에 콘테이너의 수 n이 입력된다.

두 번째 줄부터 n줄에 걸쳐서 한 줄에 하나씩 입항시간 a와 출항시간 b가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n <= 1,000,000
1 <= a <= 2n, 1 <= b <= 2n, a < b
모든 a, b는 서로 다르다.

[Sub-Task Info]
#Tiny : n <= 20
#Small : n <= 2,000
#Large : 추가제한 없음.

Output

보관할 수 있는 방법의 수를 10억 7로 나눈 나머지를 출력한다.

IO Example

입력
4
1 3
2 5
4 8
6 7

출력
4

* 설명:
보관소를 각각 A, B라고 할 때,
1, 2, 3, 4의 콘테이너에 대해서 순서대로 A, B, A, A으로 보관한다.
1, 2, 3, 4의 콘테이너에 대해서 순서대로 A, B, A, B로 보관한다.
1, 2, 3, 4의 콘테이너에 대해서 순서대로 B, A, B, A으로 보관한다.
1, 2, 3, 4의 콘테이너에 대해서 순서대로 B, A, B, B로 보관한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]