kangaroo - カンガルー Editorial /

Time Limit: 2 sec / Memory Limit: 64 MiB

配点 : 100 点

問題文

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

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

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

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

課題

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

制約

  • 1 \leqq N \leqq 300:カンガルーの匹数.
  • 1 \leqq B_i < A_i \leqq 1\,000\,000\,000:i 匹目のカンガルーのポケットと本体のサイズ.

入力

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

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

出力

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

採点基準

採点用データのうち,配点の 50\% 分については N \leqq 30 を満たす.

採点用データのうち,配点の 70\% 分については N \leqq 70 を満たす.

入出力の例

入力例 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

Source Name

JOI 2011-2012 春季トレーニング合宿 Contest Day3