#P18888. [2026多校联测]连通块计数

[2026多校联测]连通块计数

题目描述

在一条数轴上有 nn 条线段,第 ii 条覆盖 [li,ri][l_i,r_i] 内的所有实数。对于这些线段的一个子集 SS,其权值定义为 SS 中所有线段的并在数轴上形成的连通块数目。

求所有 2n2^n 个子集的权值之和,对 109+710^9+7 取模。

输入格式

第一行包含一个正整数 nn。

接下来 nn 行,每行包含两个正整数 li,ril_i,r_i,描述一条线段。

输出格式

输出一个整数,表示权值之和对 109+710^9+7 取模的结果。

样例

3
1 6
2 3
4 5
8

数据范围

对于所有数据,1≤n≤5×1051\le n\le5\times10^5,1≤li≤ri≤1091\le l_i\le r_i\le10^9。

测试点 nn 的上限
1-2 1616
3-9 20002000
10-20 5×1055\times10^5