Director K is interested in kangaroos and has decided to observe their behavior. Director K is observing $N$ kangaroos. Each kangaroo has one pocket. The kangaroos are numbered $1, 2, \dots, N$. The body size of kangaroo $i$ is $A_i$, and the pocket size of kangaroo $i$ is $B_i$. The pocket size is smaller than the kangaroo's own body size ($A_i > B_i$).

Initially, no kangaroo is inside any other kangaroo's pocket. The kangaroos repeat the following operation until no more operations can be performed:

If there exists a pair of kangaroos $(i, j)$ such that $A_i < B_j$, kangaroo $i$ is not currently inside another kangaroo's pocket, and kangaroo $j$'s pocket does not currently contain any other kangaroo, then kangaroo $i$ enters kangaroo $j$'s pocket. At this time, it does not matter if kangaroo $i$'s pocket contains another kangaroo, or if kangaroo $j$ is already inside another kangaroo's pocket. If multiple such pairs $(i, j)$ exist, it is unknown which pair will be chosen. If kangaroo $i$ already has another kangaroo inside it, the kangaroo inside moves along with kangaroo $i$.

Given the body and pocket sizes of the kangaroos, find the number of possible final states, modulo $1\,000\,000\,007$ ($= 10^9 + 7$).

Input

Read the following from standard input:

• The first line contains an integer $N$, representing the number of kangaroos.
• The following $N$ lines contain information about the kangaroos. The $(i+1)$-th line ($1 \le i \le N$) contains two space-separated integers $A_i$ and $B_i$, where $A_i$ is the body size of the $i$-th kangaroo and $B_i$ is the pocket size of the $i$-th kangaroo.

Output

Output a single integer to standard output representing the number of possible final states, modulo $1\,000\,000\,007$ ($= 10^9 + 7$).

Constraints

• $1 \le N \le 300$
• $1 \le B_i < A_i \le 1\,000\,000\,000$

Subtasks

• 50% of the points are for test cases where $N \le 30$.
• 70% of the points are for test cases where $N \le 70$.

Examples

Input 1

5
4 3
3 1
6 5
2 1
4 2

Output 1

4

Note 1

Kangaroos 1, 2, and 5 can enter kangaroo 3's pocket. Also, kangaroo 4 can enter kangaroo 1's or kangaroo 3's pocket, and kangaroo 3 cannot enter any other kangaroo's pocket. Therefore, the possible final states are the following 4:

• Kangaroo 4 is in kangaroo 3's pocket.
• Kangaroo 4 is in kangaroo 1's pocket, and kangaroo 1 is in kangaroo 3's pocket.
• Kangaroo 4 is in kangaroo 1's pocket, and kangaroo 2 is in kangaroo 3's pocket.
• Kangaroo 4 is in kangaroo 1's pocket, and kangaroo 5 is in kangaroo 3's pocket.

Input 2

20
7 6
7 3
10 1
7 2
10 7
10 7
8 6
3 2
5 4
7 2
3 2
10 9
9 4
7 2
8 6
5 4
8 6
7 4
10 5
9 3

Output 2

21060