/
実行時間制限: 2 sec / メモリ制限: 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