P5464 Shrink the Social Circle

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$.

The first line contains an integer $n$. The next $n$ lines each contain two integers, describing the SAN value interval of a person.

Output one integer, the answer.

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