구간들

$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]$의 길이는 $\max{(q-p, 0)}$으로 정의한다.

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

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

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

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