Problem Description

There are $n$ people in a social circle. Each person has a SAN value interval $[l_i, r_i]$. If the SAN intervals of two people have a non-empty intersection, then these two people have a PY relationship.

Now we want to pick some people from the social circle to form a set $S$. If we add an edge between every pair of people in the set who have a PY relationship, then $S$ must form exactly a tree (a forest is not allowed).

How many ways are there to choose such a set? Since the answer may be very large, output it modulo $10^{9}+7$.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers, describing the SAN value interval of a person.

Output Format

Output one integer, the answer.

3
1 5
2 7
4 8

6

Hint

For $20\%$ of the testdata, $n \leq 18$.

For $40\%$ of the testdata, $n \leq 50$.

For $60\%$ of the testdata, $n \leq 200$.

For $100\%$ of the testdata, $n \leq 2000$, $1 \leq l_i < r_i \leq 4000$.

Translated by ChatGPT 5