#2011. [USACO20FEB] Help Yourself G

[USACO20FEB] Help Yourself G

题目描述

在一个数轴上有 NN 条线段,第 ii 条线段覆盖了从 lil_i 到 rir_i 的所有实数(包含 lil_i 和 rir_i)。

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

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

现在 Bessie 想要求出给定 NN 条线段的所有子集(共有 2N2^N 个)的复杂度之和对 109+710^9+7 取模的结果。

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

输入格式

第一行一个整数 NN(1≤N≤1051 \leq N \leq 10^5)。

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

输出格式

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

样例

3
1 6
2 3
4 5
8

题目来源:洛谷 P6146