← 返回题目列表

AtCoder · agc015_e

E. 青木先生孵化器

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

分数: 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