P6146 [USACO20FEB] Help Yourself G

题目描述

在一个数轴上有 $N$ 条线段，第 $i$ 条线段覆盖了从 $l_i$ 到 $r_i$ 的所有实数（包含 $l_i$ 和 $r_i$）。

定义若干条线段的并为一个包含了所有被至少一个线段覆盖的点的集合。

定义若干条线段的复杂度为这些线段的并形成的连通块的数目。

现在 Bessie 想要求出给定 $N$ 条线段的所有子集（共有 $2^N$ 个）的复杂度之和对 $10^9+7$ 取模的结果。

你也许猜到了，你需要帮 Bessie 解决这个问题。但不幸的是，你猜错了！在这道题中你就是 Bessie，而且没有人来帮助你。一切就靠你自己了！

输入格式

第一行一个整数 $N$（$1 \leq N \leq 10^5$）。

接下来 $N$ 行，每行两个整数 $l_i,r_i$，描述一条线段。保证 $1 \leq l_i \lt r_i \leq 2N$，且任意两个端点都不在同一位置上。

输出格式

输出所求答案对 $10^9+7$ 取模的结果。

输入输出样例 #1

输入 #1

3
1 6
2 3
4 5

输出 #1

8

说明/提示

样例解释

所有非空子集的复杂度如下所示（显然空集的复杂度为零）：

$$\{[1,6]\} \implies 1, \{[2,3]\} \implies 1, \{[4,5]\} \implies 1$$$$\{[1,6],[2,3]\} \implies 1, \{[1,6],[4,5]\} \implies 1, \{[2,3],[4,5]\} \implies 2$$$$\{[1,6],[2,3],[4,5]\} \implies 1$$

故答案为 $1+1+1+1+1+2+1=8$。

子任务

• 测试点 $2 \sim 3$ 满足 $N \leq 16$；
• 测试点 $4 \sim 7$ 满足 $N \leq 1000$；
• 测试点 $8 \sim 12$ 没有特殊限制。