样例下载

题目描述

一个集合内含有若干个闭区间，定义这个集合的价值为集合内所有区间的并形成的连通块的数目。

例如集合 $\{[1,3], [2,4], [5,6]\}$ 的价值为 $2$.

现在给出一个集合，该集合包含数轴上的 $N$ 个闭区间 $[L_i, R_i]$ ，求该集合的所有子集（共有 $2^N$ 个）的价值之和。答案可能很大，你只需要输出其 $mod$ $(10^9+7)$ 的值。

输入格式

第一行：一个整数 $N$。

接下来 $N$ 行，每行两个整数 $L_i,R_i$，描述一个区间。保证 $1 ≤ L_i < R_i ≤ 2N$，且任意两个区间的端点不重合。

输出格式

一个整数，表示答案 $mod$ $(10^9+7)$

样例输入

3
1 6
2 3
4 5

样例输出

8

数据范围

• $20\%$ 的数据满足 $N ≤ 20$；
• $40\%$ 的数据满足 $N ≤ 10^3$；
• $100\%$ 的数据满足$1 ≤ N ≤ 10^5, 1 ≤ L_i < R_i ≤ 2N$。