002 - 港湾設備 (Port Facility)

JOI 港には毎日たくさんのコンテナが船で運ばれてきて, 全国各地へとトラックで運ばれていく．

JOI 港は非常に狭く, コンテナを積んでおける区画が 2 つしかない．それぞれの区画には, コンテナを縦にいくらでも積んでおくことができる．

作業の安全のため, 船で運ばれてきたコンテナは, どちらかの区画に積まなければならない．その区画にすでにコンテナが積まれている場合は, すでに積まれているコンテナの一番上に積まなければならない．トラックで運ぶときは, どちらかの区画に積まれたコンテナの一番上から順番に運んでいかなければならない．

本日，JOI 港には, N 個のコンテナが船で運ばれてくる予定である．そのすべての荷物が本日中にトラックで運ばれていく．

あなたは JOI 港の港湾設備の管理を任されており, すべてのコンテナが船で運ばれてくる時刻と, トラックで運ばれていく時刻を知っている．コンテナを積み降ろしする方法は何通りあるかを 1 000 000 007 で割った余りを求めるプログラムを作成せよ．

課題

JOI 港に運ばれてくるコンテナの個数と, それぞれのコンテナの運ばれてくる時刻と運ばれていく時刻が与えられたとき, コンテナを積み降ろしする方法は何通りあるかを 1 000 000 007 で割った余りを求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

• 1 行目には，整数 N が書かれており, JOI 港に船で運ばれてくるコンテナの個数を表す．
• 続く N 行のうちの i 行目(1 ≤ i ≤ N) には，整数 A_i, B_i が空白を区切りとして書かれている．これは，i 番目のコンテナは時刻 A_i に JOI 港に船で運ばれてきて，時刻 B_i にトラックで運ばれていくことを表す．

出力

標準出力に, コンテナを積み降ろしする方法は何通りあるかを 1 000 000 007 で割った余りを 1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 ≤ N ≤ 1 000 000．
• 1 ≤ A_i ≤ 2N (1 ≤ i ≤ N)．
• 1 ≤ B_i ≤ 2N (1 ≤ i ≤ N)．
• A_i < B_i (1 ≤ i ≤ N)．
• N 個の整数 A₁, ..., A_N, B₁, ..., B_N は互いに異なる．

小課題

この課題では小課題は全部で 4 個ある．各小課題の配点および追加の制限は以下の通りである．

小課題1 [10 点]

• N ≤ 20．

小課題2 [12 点]

• N ≤ 2 000．

小課題3 [56 点]

• N ≤ 100 000．

小課題4 [22 点]

追加の制限はない．

入出力例

入力例 1

4
1 3
2 5
4 8
6 7

出力例 1

4

この入力例では, 4 通りの積み降ろしの方法が存在する．2 つの区画を A, B とする．条件を満たす積み方は以下の通りである．

• 1, 2, 3, 4 番目のコンテナを, 順に，A, B, A, A の区画に積む．
• 1, 2, 3, 4 番目のコンテナを, 順に，A, B, A, B の区画に積む．
• 1, 2, 3, 4 番目のコンテナを, 順に，B, A, B, A の区画に積む．
• 1, 2, 3, 4 番目のコンテナを, 順に，B, A, B, B の区画に積む．

入力例 2

3
1 4
2 5
3 6

出力例 2

0

入力例 3

5
1 4
2 10
6 9
7 8
3 5

出力例 3

8

入力例 4

8
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12

出力例 4

16