问题 5035 --导出子图

5035: 导出子图

题目描述

  给定 $n$ 个区间,第 $i$ 个区间是 $[l_r,r_i]$。

接着,我们构造一个无向图 $G=(V,E)$,其中点集 $V=\{1,2, \dots, n\}$,边集 $E=\{(u,v)~|~1\leq u,v\leq n, [l_u,r_u]\cap [l_v,r_v] \neq \varnothing\} $ 。
即在图 $G$ 中 $u,v$ 之间有连边,当且仅当 $u,v$ 对应的区间有交。

我们定义一个图 $G$ 的导出子图为满足点集  $V'\subseteq V(V'\neq \varnothing)$,且边集 $E'=\{(u,v)~|~u\in V', v\in V', (u,v)\in E\}$ 的图 $G'=(V',E')$。
即由图 $G$ 顶点的一个非空子集和该图中两端均在该子集的所有边的集合组成的图即为图 $G$ 的导出子图。

求 $G$ 有多少个不同的导出子图 $G'$,使得 $G'$ 是一棵树。答案对 $10^9+7$ 取模。

输入

第一行一个整数 $n$。
接下来 $n$ 行,每行两个整数 $l_i$ 和 $r_i$。

输出

输出一行一个整数表示答案。答案对 $10^9+7$ 取模。

样例输入输出

输入#1 复制
3
1 5
2 7
4 8
输出#1 复制
6
输入#2 复制
7
3 14
1 59
26 53
58 979
323 846
264 338
32 795
输出#2 复制
38

提示

样例解释 1
连边 $(1,2),(1,3),(2,3)$。

不难发现合法的连通子图的点集有 $6$ 个:$\{1\}$、$\{2\}$、$\{3\}$、$\{1,2\}$、$\{1,3\}$、$\{2,3\}$。


本题采用子任务捆绑测试。对于某个子任务,你只有通过了这个子任务的所有测试点,才能获得这个子任务的分数。

子任务 1(25 分):$n \leq 18$。
子任务 2(25 分):$n \leq 58$。
子任务 3(25 分):$n \leq 200$。
子任务 4(25 分):无特殊限制。
对于所有数据,$1 \leq n \leq 2000$,$1 \leq l_i \leq r_i \leq 4000 $。

序号 标题 作者 发表时间 费用 订购数 操作