시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

K 理事長はカンガルーに興味を持ち,カンガルーの行動を観察することにした.K 理事長は N 匹のカン ガルーを観察している.カンガルーにはポケットが一つずつ付いている.カンガルーには 1, 2, ··· , N の番 号が付けられている.カンガルー i の本体のサイズは Ai であり,カンガルー i のポケットのサイズは Bi で ある.ポケットのサイズはそのカンガルーの本体のサイズより小さい (Ai > Bi).

最初にどのカンガルーのポケットの中にも他のカンガルーは入っていない.カンガルーは以下の操作を 操作ができなくなるまで 繰り返す.

Ai < Bj を満たすカンガルー i とカンガルー j の組であって,カンガルー i が他のカンガルーのポケット の中ではなく,カンガルー j のポケットの中に他のカンガルーがいないようなものが存在するとき,カン ガルー i はカンガルー j のポケットの中に入る.このとき,カンガルー i のポケットの中に他のカンガルー がいても,カンガルー j が他のカンガルーのポケットの中にいても構わない.そのような (i, j) の組が複数 存在するとき,どの組が選ばれるか分からない.カンガルー i の中に他のカンガルーが入っている場合,中 のカンガルーはカンガルー i と一緒に移動する.

与えられたカンガルーの本体とポケットのサイズに対して,最後の状態が何通りあるかを 1 000 000 007 (= 109 + 7) で割った余りを求めたい.

カンガルーの本体とポケットのサイズが与えられたとき,最後の状態が何通りあるかを 1 000 000 007 (= 109 + 7) で割った余りを求めるプログラムを作成せよ.

입력

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

  • 1 行目には整数 N が書かれている.N はカンガルーの匹数を表す.
  • 続く N 行にはカンガルーの情報が書かれている.i + 1 行目 (1 ≤ i ≤ N) には 2 つの整数 Ai, Bi が空白 を区切りとして書かれている.Ai は i 匹目のカンガルーの本体のサイズを,Bi は i 匹目のカンガルー のポケットのサイズをそれぞれ表す.

출력

標準出力に,最後の状態が何通りあるかを 1 000 000 007 (= 109 + 7) で割った余りを表す整数を 1 行に出 力せよ.

제한

  • 1 ≤ N ≤ 300 カンガルーの匹数
  • 1 ≤ Bi < Ai ≤ 1 000 000 000 i 匹目のカンガルーのポケットと本体のサイズ

예제 입력 1

5
4 3
3 1
6 5
2 1
4 2

예제 출력 1

4

カンガルー 1,カンガルー 2,およびカンガルー 5 はカンガルー 3 のポケットに入ることができる.また カンガルー 4 はカンガルー 1 またはカンガルー 3 のポケットに入ることができ,カンガルー 3 は他のどの カンガルーのポケットにも入ることはできない.よって,最後の状態としてありうるのは以下の 4 通りで ある.

  • カンガルー 4 がカンガルー 3 のポケットに入っている.
  • カンガルー 4 はカンガルー 1 のポケットに入っており,カンガルー 1 はカンガルー 3 のポケットに 入っている.
  • カンガルー 4 はカンガルー 1 のポケットに入っており,カンガルー 2 はカンガルー 3 のポケットに 入っている.
  • カンガルー 4 はカンガルー 1 のポケットに入っており,カンガルー 5 はカンガルー 3 のポケットに 入っている.

예제 입력 2

20
7 6
7 3
10 1
7 2
10 7
10 7
8 6
3 2
5 4
7 2
3 2
10 9
9 4
7 2
8 6
5 4
8 6
7 4
10 5
9 3

예제 출력 2

21060