问题

随着2015年即将结束，市区已被点亮以庆祝年末。今年，猫Snuke也喜欢为市区制作一个照明装置。

市区可以看作是一个一维数字线。在这个数线上安装了$N$个灯。当第$i_{th}$个灯的电源打开时，它可以照亮一个区间\[l_i, r_i\]（包括边界）。

尽管猫Snuke可以根据自己的意愿独立地打开这$N$个灯，但他想尝试尽可能多的不同照明组合。然后，如果我们已经尝试了所有$2^N$种照明组合，我们想知道有多少种不同的照明组合，其中每个组合都是由一个或多个灯照亮的点的集合。

当我们尝试了所有的$2^N$种照明组合时，请回答不同的照明组合的数量，对$1,000,000,007$取模。

输入

输入将通过标准输入以以下格式给出

$N$ $l_1$ $r_1$ $l_2$ $r_2$ : $l_N$ $r_N$

• 在第一行中，用空格分隔给出一个整数$N(1≦N≦2,000)$。
• 从第二行开始，有$N$行附加行，用于提供有关照明范围的信息。对于第$i_{th}$行，用空格分隔给出整数$l_i,r_i(0≦l_i<r_i≦1,000,000,000)$。

输出

请回答不同的照明组合的数量，对$1,000,000,007$取模。

在输出结束时打印一个换行符。

输入示例 1

4
0 1
1 2
0 2
1 3

输出示例 1

6

共有16种不同的灯光连接方式，但只有6种不同的照明组合，$\\{φ\\}, \\{\[0, 1\]\\}, \\{\[1, 2\]\\}, \\{\[0, 2\]\\}, \\{\[1, 3\]\\}, \\{\[0, 3\]\\}$。

输入示例 2

12
0 4
7 12
1 3
6 8
2 3
4 6
8 9
2 7
9 11
1 2
3 5
7 9

输出示例 2

240

输入示例 3

14
0 1
2 3
4 5
6 7
8 9
10 11
12 13
14 15
16 17
18 19
0 3
4 7
8 13
14 19

输出示例 3

2025