시간 제한메모리 제한제출정답맞힌 사람정답 비율
4.5 초 1024 MB105422632.500%

## 문제

Many containers are transported by ships to the JOI Port every day. They are transported to all over the country by trucks.

The JOI Port is very narrow. It has only two areas where we can put containers. In each area, we can put any number of containers vertically.

For safety reasons, when a container is transported by a ship, we have to put it on one of the areas. If some containers are already put there, we have to put it on the top of them. When we transport a container by a truck, we have to take a container from the top of the containers on one of the areas.

Today, N containers will be transported to the JOI Port. All of them will be transported by trucks.

Your task is to manage the facilities of the JOI Port. For each container, you know when it will come and when it will leave. Write a program which calculates the number of ways to put and take containers modulo 1 000 000 007.

Given the number of containers transported to the JOI Port and the time for each container to come and leave, write a program which calculates the number of ways to put and take containers satisfying the conditions modulo 1 000 000 007.

## 입력

Read the following data from the standard input.

• The first line of input contains an integer N, the number of containers transported to the JOI Port.
• The i-th line (1 ≤ i ≤ N) of the following N lines contains two space separated integers Ai, Bi. This means the i-th container will come to the JOI Port at time Ai, and leave the JOI Port by a truck at time Bi.

## 출력

Write one line to the standard output. The output contains the number of ways to put and take containers satisfying the conditions modulo 1 000 000 007.

## 제한

• 1 ≤ N ≤ 1 000 000.
• 1 ≤ Ai ≤ 2N (1 ≤ i ≤ N).
• 1 ≤ Bi ≤ 2N (1 ≤ i ≤ N).
• Ai < Bi (1 ≤ i ≤ N).
• The 2N integers A1, · · · , AN, B1, · · · , BN are different from each other.

번호 배점 제한
1 10

N ≤ 20.

2 12

N ≤ 2 000.

3 56

N ≤ 100 000.

4 22

## 예제 입력 1

4
1 3
2 5
4 8
6 7


## 예제 출력 1

4


There are 4 ways to put and take containers. Denote the areas by A, B. The following ways to put containers satisfy the condition.

• Put 1, 2, 3, 4-th container to the area A,B,A,A, respectively.
• Put 1, 2, 3, 4-th container to the area A,B,A,B, respectively.
• Put 1, 2, 3, 4-th container to the area B,A,B,A, respectively.
• Put 1, 2, 3, 4-th container to the area B,A,B,B, respectively.

## 예제 입력 2

3
1 4
2 5
3 6


## 예제 출력 2

0


## 예제 입력 3

5
1 4
2 10
6 9
7 8
3 5


## 예제 출력 3

8


## 예제 입력 4

8
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12


## 예제 출력 4

16


## 채점 및 기타 정보

• 예제는 채점하지 않는다.