Help Yourself (Gold)

문제

Bessie has been given $NN$ segments ($1\le N\le {10}^{5}1\backslash le\; N\backslash le\; 10^5$) on a 1D number line. The $ii$th segment contains all reals $xx$ such that $l_i\le x\le r_{i}l\_i\backslash le\; x\backslash le\; r\_i$.

Define the union of a set of segments to be the set of all $xx$ that are contained within at least one segment. Define the complexity of a set of segments to be the number of connected regions represented in its union.

Bessie wants to compute the sum of the complexities over all $2^{N}2^N$ subsets of the given set of $NN$ segments, modulo ${10}^9+710^9+7$.

Normally, your job is to help Bessie. But this time, you are Bessie, and there's no one to help you. Help yourself!

입력

The first line contains $NN$.

Each of the next $NN$ lines contains two integers $l_{i}l\_i$ and $r_{i}r\_i$. It is guaranteed that and all $l_i,r_{i}l\_i,r\_i$ are distinct integers in the range $1\dots 2N\mathrm{.}1\; \backslash ldots\; 2N.$

출력

Output the answer, modulo ${10}^9+710^9+7$.

힌트

The complexity of each nonempty subset is written below.

$$\{[1,6]\}⟹1,\{[2,3]\}⟹1,\{[4,5]\}⟹1\backslash \{[1,6]\backslash \}\; \backslash implies\; 1,\; \backslash \{[2,3]\backslash \}\; \backslash implies\; 1,\; \backslash \{[4,5]\backslash \}\; \backslash implies\; 1$$

$$\{[1,6],[2,3]\}⟹1,\{[1,6],[4,5]\}⟹1,\{[2,3],[4,5]\}⟹2\backslash \{[1,6],[2,3]\backslash \}\; \backslash implies\; 1,\; \backslash \{[1,6],[4,5]\backslash \}\; \backslash implies\; 1,\; \backslash \{[2,3],[4,5]\backslash \}\; \backslash implies\; 2$$

$$\{[1,6],[2,3],[4,5]\}⟹1\backslash \{[1,6],[2,3],[4,5]\backslash \}\; \backslash implies\; 1$$

The answer is $1+1+1+1+1+2+1=81+1+1+1+1+2+1=8$.

3
1 6
2 3
4 5

8