题目描述

在数轴上有 $N$ 个高桥君排成一排，他们的编号从 $1$ 到 $N$。第 $i$ 个高桥君在时刻 $0$ 时位于位置 $X_i$，并以速度 $V_i$ 向正方向开始行走。

「けすぬ君」可以在时刻 $0$ 时，从所有高桥君中选择若干人，将他们变成青木君。即使高桥君变成青木君，他们的行走速度也不会改变。之后，如果某一时刻某个高桥君和青木君位于同一位置，这个高桥君也会变成青木君。

在 $2^N$ 种初始将高桥君变为青木君的方法中，有多少种方法能使得在足够长时间后，所有高桥君全部都变为青木君？请将这个数对 $10^9+7$ 取模后输出。

输入格式

输入按以下格式从标准输入给出。

$N$
$X_1$ $V_1$
$X_2$ $V_2$
$\vdots$
$X_N$ $V_N$

输出格式

输出一个整数，表示在足够长时间后所有高桥君都变成青木君的方法数，对 $10^9+7$ 取模。

样例 1

输入

3
2 5
6 1
3 7

输出

6

样例 2

输入

4
3 7
2 9
8 16
10 8

输出

9

说明/提示

限制条件

• $1 \leq N \leq 200000$
• $1 \leq X_i, V_i \leq 10^9 \ (1 \leq i \leq N)$
• $X_i$ 互不相同
• $V_i$ 互不相同

样例解释 1

当けすぬ君选择第 $(2), (3), (1,2), (1,3), (2,3), (1,2,3)$ 个高桥君变成青木君时，经过足够长时间后，所有高桥君都会变成青木君。

由 ChatGPT 5 翻译