부분 집합의 복잡도

실행 시간 제한	메모리 제한
2 초	512 MB

1차원 숫자 선상에 $N$ 개의 선분( $1 \le N \le 10^5$ )이 주어졌습니다. $i$ 번째 선분은 $l_i \le x \le r_i$ 인 모든 실수 $x$ 를 포함합니다.

선분들의 집합의 합집합을 정의하면, 적어도 하나의 선분에 포함된 모든 $x$ 의 집합입니다.

선분들의 집합의 복잡도를 정의하면, 그 합집합을 이루는 연결된 구간의 수입니다.

현재 주어진 $N$ 개의 선분의 집합에 대해, 가능한 모든 $2^N$ 개의 부분 집합을 고려하여, 각 부분집합의복잡도를 모두 더한 값을 계산하려고 합니다, 결과값은 $10^9+7$ 로 나눈 나머지를 구합니다.

첫 번째 줄에는 $N$ 이 포함되어 있습니다.

다음 $N$ 줄 각각에는 두 개의 정수 $l_i$ 와 $r_i$ 가 포함됩니다. 보장된 $l_i\lt r_i$ 와 모든 $l_i,r_i$ 는 범위 $1 \ldots 2N$ 내의 고유한 정수입니다.

결과값을 $10^9+7$ 로 나눈 나머지를 출력하십시오.

각 비어 있지 않은 부분 집합의 복잡성은 아래에 작성되어 있습니다.

$\{[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$

답변은 $1+1+1+1+1+2+1=8$ 입니다.