问题
年底 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