Port Facility

Time limit4.5sMemory limit1024 MB

Summary

Count the ways to assign each container to one of two stacks so that each stack removes containers in last-in-first-out order, modulo 1000000007.

Level: Medium7 of 10
Topics: Intervals, Stack, Union-find
Solved: No attempts yet

Problem

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

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

For safety reasons, when a container is brought in by ship, it must be placed in one of the two areas. If containers are already there, it goes on top of them. When a container is taken out by truck, it must be taken from the top of the containers in one of the areas.

Today, N containers will arrive at the JOI Port. All of them will leave by truck.

You manage the facilities of the JOI Port. For each container, you know when it arrives and when it leaves. Write a program that counts the number of ways to place and remove containers, modulo 1 000 000 007.

Input

The first line contains an integer N, the number of containers.

Each of the following N lines contains two space-separated integers Ai and Bi. Container i arrives at time Ai and leaves by truck at time Bi.

Output

Print one line containing the number of ways to place and remove containers, modulo 1 000 000 007.

Constraints

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 all different from each other.

Examples4

Example 1
Input
```
4
1 3
2 5
4 8
6 7
```
Expected output
```
4
```
Example 2
Input
```
3
1 4
2 5
3 6
```
Expected output
```
0
```
Example 3
Input
```
5
1 4
2 10
6 9
7 8
3 5
```
Expected output
```
8
```

Example 4

Input

Expected output