P6146 [USACO20FEB] Help Yourself G

There are $N$ segments on a number line. The $i$-th segment covers all real numbers from $l_i$ to $r_i$ (including $l_i$ and $r_i$). Define the **union** of some segments as the set of all points that are covered by at least one segment. Define the **complexity** of some segments as the number of connected components formed by the union of these segments. Now Bessie wants to compute, for all subsets of the given $N$ segments (there are $2^N$ in total), the sum of their complexities, and output the result modulo $10^9+7$. You might have guessed that you need to help Bessie solve this problem. But unfortunately, you guessed wrong! In this problem, you are Bessie, and nobody will help you. It is all up to you.

The first line contains an integer $N$ ($1 \leq N \leq 10^5$). The next $N$ lines each contain two integers $l_i, r_i$, describing a segment. It is guaranteed that $1 \leq l_i \lt r_i \leq 2N$, and no two endpoints are at the same position.

Output the required answer modulo $10^9+7$.

### Sample Explanation The complexities of all non-empty subsets are as follows (clearly, the empty set has complexity $0$): $$ \{[1,6]\} \implies 1, \{[2,3]\} \implies 1, \{[4,5]\} \implies 1 $$ $$ \{[1,6],[2,3]\} \implies 1, \{[1,6],[4,5]\} \implies 1, \{[2,3],[4,5]\} \implies 2 $$ $$ \{[1,6],[2,3],[4,5]\} \implies 1 $$ So the answer is $1+1+1+1+1+2+1=8$. ### Subtasks - Test points $2 \sim 3$ satisfy $N \leq 16$. - Test points $4 \sim 7$ satisfy $N \leq 1000$. - Test points $8 \sim 12$ have no special constraints. Translated by ChatGPT 5