AtCoder Grand Contest 015

E - Mr.Aoki Incubator


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 1200

問題文

数直線上に N 人の高橋君が並んでおり、1 から N までの番号がついています。 i 人目の高橋君は、時刻 0 に位置 X_i にいて、速度 V_i で正の方向に歩き始めます。

けすぬ君は、時刻 0 に高橋君たちのうちの何人かを選んで青木君にすることができます。 高橋君が青木君になっても歩く速度は変化しません。 それ以降、もしある瞬間に高橋君と青木君が同じ座標にいたなら、高橋君は青木君になります。

けすぬ君が時刻 0 に高橋君を青木君にする 2^N 通りの方法のうち、 十分な時間が経過した後、高橋君が全員青木君になっているような方法の数を 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

出力

十分な時間が経過した後、高橋君が全員青木君になっているような方法の数を 10^9+7 で割ったあまりを出力せよ。


入力例 1

3
2 5
6 1
3 7

出力例 1

6

けすぬ君が (2),(3),(1,2),(1,3),(2,3),(1,2,3) 番目の高橋君を青木君にしたとき、十分な時間が経過した後にすべての高橋君が青木君になっています。


入力例 2

4
3 7
2 9
8 16
10 8

出力例 2

9

Score : 1200 points

Problem Statement

Takahashi is an expert of Clone Jutsu, a secret art that creates copies of his body.

On a number line, there are N copies of Takahashi, numbered 1 through N. The i-th copy is located at position X_i and starts walking with velocity V_i in the positive direction at time 0.

Kenus is a master of Transformation Jutsu, and not only can he change into a person other than himself, but he can also transform another person into someone else.

Kenus can select some of the copies of Takahashi at time 0, and transform them into copies of Aoki, another Ninja. The walking velocity of a copy does not change when it transforms. From then on, whenever a copy of Takahashi and a copy of Aoki are at the same coordinate, that copy of Takahashi transforms into a copy of Aoki.

Among the 2^N ways to transform some copies of Takahashi into copies of Aoki at time 0, in how many ways will all the copies of Takahashi become copies of Aoki after a sufficiently long time? Find the count modulo 10^9+7.

Constraints

  • 1 ≤ N ≤ 200000
  • 1 ≤ X_i,V_i ≤ 10^9(1 ≤ i ≤ N)
  • X_i and V_i are integers.
  • All X_i are distinct.
  • All V_i are distinct.

Input

The input is given from Standard Input in the following format:

N
X_1 V_1
:
X_N V_N

Output

Print the number of the ways that cause all the copies of Takahashi to turn into copies of Aoki after a sufficiently long time, modulo 10^9+7.


Sample Input 1

3
2 5
6 1
3 7

Sample Output 1

6

All copies of Takahashi will turn into copies of Aoki after a sufficiently long time if Kenus transforms one of the following sets of copies of Takahashi into copies of Aoki: (2), (3), (1,2), (1,3), (2,3) and (1,2,3).


Sample Input 2

4
3 7
2 9
8 16
10 8

Sample Output 2

9

Submit提出する