分数: 1200 点
问题陈述
高桥是克隆术专家,这是一种复制他身体的秘密艺术。
在数轴上,有 N 高桥的副本,编号 1 通过 N。 的 网格的 i第一个副本位于位置 X_i 并开始快速行走 V_i 时间正方向 0.
肯努斯是一名变形之术高手,他不仅可以变成自己以外的人,还可以将别人变成别人。
肯纳斯可以同时选择高桥的一些副本 0,并将它们转化为另一个忍者青木的复制品。 副本的行走速度在变形时不会改变。 从那时起,每当高桥的副本和青木的副本处于同一坐标时,高桥的副本就会变成青木的副本。
其中 2^N 将高桥的一些副本转换为青木副本的方法 0,经过足够长的时间后,所有高桥的副本有多少种方式会变成青木的副本? 求计数模数 10^9+7.
约束
- 1 ≤ N ≤ 200000
- 1 ≤ X_i,V_i ≤ 10^9(1 ≤ i ≤ N)
- X_i 和 V_i 是整数。
- 全部 X_i 是不同的。
- 全部 V_i 是不同的。
输入
输入由标准输入按以下格式给出:
N X_1 V_1 : X_N V_N
输出
打印在足够长的时间后导致所有 Takahashi 副本变成 Aoki 副本的方式数,模 10^9+7.
示例输入 1
3 2 5 6 1 3 7
示例输出 1
6
如果 Kenus 将以下一组高桥副本转换为青木副本,则在足够长的时间后,所有高桥副本都将变成青木副本: (2), (3), (1,2), (1,3), (2,3) 和 (1,2,3).
示例输入 2
4 3 7 2 9 8 16 10 8
示例输出 2
9