25026번 - 구간들

$p$이상 $q$이하인 모든 실수의 집합을 $[p,q]$로 나타낸다. 이를 구간이라고 한다. $p > q$일 수 있으며, 이 때 집합은 공집합인 것에 주의하라.

$k$개의 구간 $[p_1, q_1]$, $[p_2, q_2]$, $\cdots$, $[p_k,q_k]$의 교집합은 $P = \max{(p_1, p_2, \cdots , p_k)}$, $Q = \min{(q_1, q_2, \cdots , q_k)}$라고 할 때, $P$이상 $Q$이하인 집합이므로, 구간 $[P,Q]$로 나타낼 수 있다.

어떤 구간 $[p,q]$의 길이는 $\max{(q-p, 0)}$으로 정의된다.

$N$개의 구간 $I_1$, $I_2$, $\cdots$, $I_N$이 주어진다. $l_i = [s_i,e_i]$이다. $I_i$중에서 한 개이상의 구간을 선택하는 $2^N-1$가지의 모든 방법에 대해, 선택된 구간들의 교집합 길이의 합과 길이가 $1$이상인 교집합의 개수를 구하는 프로그램을 작성하라.

첫 번째 줄에 주어지는 구간의 개수를 나타내는 하나의 정수 $N$($1 ≤ N ≤ 10^5$)이 주어진다.

다음 $N$개의 줄의 $i$번째 줄에는 $I_i$의 정보를 나타내는 두 정수 $s_i$, $e_i$($0 ≤ s_i, e_i ≤ 10^9$)가 공백 하나로 구분되어 주어진다. $I_i = [s_i, e_i]$인 것이다.

첫 번째 줄에 주어진 구간 중에서 한 개이상의 구간을 선택하는 $2^N-1$가지의 모든 방법에 대해, 선택된 구간들의 교집합 길이의 합과 길이가 $1$이상인 교집합의 개수를 공백 하나로 구분하여 출력한다. 이 수들은 매우 클 수 있으므로, $1\,000\,000\,007$로 나눈 나머지를 출력하도록 한다.