17774번 - Kangaroo 다국어

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⁹ + 7) で割った余りを求めたい．

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

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

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

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

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