← 返回题目列表

AtCoder · code_festival_2015_okinawa_h

H. 2015 年快乐

中文机器翻译题面 查看原题

问题

年底 2015 临近,市中心已张灯结彩,喜迎岁末。今年,Cat Snuke 还喜欢为市中心制作一个发光装置。

市中心可以被视为一维数字线。 已安装在此数轴上的 N 灯。当电源的 i_{th} 灯亮,可以照亮一段时间 [l_i, r_i] (含)。

虽然 Cat 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