구간들

$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$로 나눈 나머지를 출력하도록 한다.