Kangaroo(カンガルー) - joi2012-day3

時間制限: 2秒

メモリ制限: 64MB

K 理事長はカンガルーに興味を持ち，カンガルーの行動を観察することにした．K 理事長は N 匹のカンガルーを観察している．カンガルーにはポケットが一つずつ付いている．カンガルーには 1, 2, …, 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	出力例1
`5 4 3 3 1 6 5 2 1 4 2`	`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	出力例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`	`21060`