0400 - ボート (boat)

ソウル市には漢江 (Han River) と呼ばれる川が東西方向に流れている. 漢江の北側の岸には, N 校のボート学校があり, 西から東の順に 1 から N までの番号が付けられている. 同じ学校のボートは全く同じ色であり, 見分けることができない. また, 異なる学校のボートは異なる色であり, 常に見分けることができる. 番号 i の学校は, 祭にボートを出さないかもしれない. もし, 学校 i が祭にボートを出す場合, 出す数は a_i 艘以上 b_i 艘以下のいかなる数にもなり得る (a_i ≤ b_i).

さらに, 次の条件を満たさなければならない. 番号 i の学校が祭にボートを出す場合, 出すボートの数は, 番号が i より小さく祭にボートを出すどの学校が出すボートの数よりも 大きくなければならない.

課題 (Task)

各学校に対する a_i, b_i の値が与えられたとき, 少なくとも 1 校の学校がボートを出す場合の, 学校が祭にボートを出す方法の個数を求めよ.

入力 (Input)

入力の 1 行目は, 学校の数を表す 1 個の整数 N を含む. 続く N 行のうちの i 行目は, 2 個の整数 a_i, b_i (1 ≤ a_i ≤ b_i ≤ 10⁹) を含む.

出力 (Output)

出力は 1 行からなり, 学校が祭にボートを出す方法の個数を 1,000,000,007 で割った余りを含む.

例 (Example)

入力 (Input)

2
1 2
2 3

出力 (Output)

7

注釈 (Comments)

片方の学校のみがボートを出す方法が 4 通りある. また, 両方の学校がボートを出す方法が 3 通りある. 従って, 正解は 7 である.

採点方法 (Scoring)

小課題 1 (9 点)

1 ≤ N ≤ 500 を満たし, かつ, 全ての 1 ≤ i ≤ N に対して a_i = b_i を満たす.

小課題 2 (22 点)

1 ≤ N ≤ 500 を満たし, かつ, Σ_{1 ≤ i ≤ N} (b_i - a_i) ≤ 10⁶ を満たす.

小課題 3 (27 点)

1 ≤ N ≤ 100 を満たす.

小課題 4 (42 点)

1 ≤ N ≤ 500 を満たす.