/*
题意：求所有线段子集的并集连通块数量之和。
思路：每个连通块由左端点最小的线段唯一代表。扫描端点，当遇到第 k 个左端点时，
已有 c 条线段完全结束。让当前线段成为新连通块起点的方案数为 2^(c+n-k)。
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int mod=1000000007;

int l[200005];
int r[200005];
ll pw[100005];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int x,y;
        cin >> x >> y;

        l[x] = 1;
        r[y] = 1;
    }

    pw[0] = 1;

    for (int i = 1; i <= n; i++)
        pw[i] = pw[i - 1] * 2 % mod;

    ll ans = 0;
    int c = 0;
    int k = 0;

    for (int i = 1; i <= 2 * n; i++) {
        if (l[i]) {
            k++;
            ans = (ans + pw[c + n - k]) % mod;
        }

        if (r[i]) c++;
    }

    cout << ans;

    return 0;
}

解题思路

直接枚举每个子集显然不行，因为一共有 $2^N$ 个子集。

考虑把答案改成计算每条线段的贡献。

对于任意一个子集，它的每个连通块中一定存在一条左端点最小的线段，而且这条线段唯一。因此，可以把这个连通块的贡献记在这条线段上。

于是问题变成：

对于每条线段，计算有多少个子集使它成为某个连通块中左端点最小的线段。

按照坐标从左到右扫描所有端点。当扫描到某条线段的左端点时，设：

• 它是第 $k$ 个出现左端点的线段；
• 已经有 $c$ 条线段的右端点出现，即这些线段已经完全位于当前线段左侧；
• 还有 $k-1-c$ 条更早开始，但尚未结束的线段。

这 $k-1-c$ 条尚未结束的线段都与当前线段相交。如果选择了其中任意一条，当前线段就会和左端点更小的线段连通，不能成为一个新连通块的起点。

因此这些线段必须全部不选。

其他线段的选择情况如下：

• 当前线段必须选择；
• 已经结束的 $c$ 条线段可以任意选择，共 $2^c$ 种；
• 尚未开始的 $n-k$ 条线段可以任意选择，共 $2^{n-k}$ 种；
• 与当前线段相交的早期线段必须全部不选，只有一种选择。

所以当前线段的贡献为

把每个左端点产生的贡献相加即可。

例如样例中：

• 扫描到 $1$ 时，$k=1,c=0$，贡献为 $2^{0+3-1}=4$；
• 扫描到 $2$ 时，$k=2,c=0$，贡献为 $2^{0+3-2}=2$；
• 扫描到 $4$ 时，区间 $[2,3]$ 已结束，$k=3,c=1$，贡献为 $2^{1+3-3}=2$。

总答案为 $4+2+2=8$。

时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。