Summing the Union Complexity of Interval Subsets

You are given N line segments on the real line. The i-th segment covers all points from \(l_i\) to \(r_i\) (inclusive). For any subset of these segments (there are \(2^N\) subsets in total, including the empty set), define the union as the set of points that are covered by at least one segment in the subset.

The complexity of a subset is defined as the number of connected components (maximal continuous intervals) in the union. Note that the union of the empty set is empty and its complexity is \(0\).

Your task is to compute the sum of the complexity over all \(2^N\) subsets, and output the answer modulo \(10^9+7\).

For a non‐empty subset, if we sort the chosen segments by their left endpoints, the union will consist of one or more connected components. In fact, if a subset has its segments partitioned into connected components, then its complexity is equal to the number of connected components. One useful observation is that every non‐empty subset contributes at least \(1\) (for the first connected component) plus contributions for each gap between consecutive segments which do not overlap.

A key insight is that if we sort all segments by their left endpoints (i.e. let the sorted order be \(1,2,\dots,N\)), and define for each segment \(j\) a parameter \[ p[j] = \max\{i \mid i < j \text{ and } r_i < l_j\}, \] with the convention that \(p[j]=0\) if no such index exists, then one may show that the overall answer is given by \[ \text{Answer} = \sum_{j=1}^{N} 2^{p[j] + (N-j)} \pmod{10^9+7}. \]

Your program should compute this sum.

Note: The empty subset contributes \(0\) to the sum.

inputFormat

The input begins with a single integer \(N\) (the number of segments). The following \(N\) lines each contain two integers \(l_i\) and \(r_i\) representing the endpoints of the \(i\)-th segment.

It is guaranteed that the segments may be processed in any order. You should sort them by their left endpoint \(l_i\) before processing.

outputFormat

Output a single integer: the sum of the complexity of the unions of all subsets of segments, taken modulo \(10^9+7\).

sample

2
1 2
2 3

3