2567 [APIO 2016] ボート

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

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

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

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

出力は 1 行からなり，学校が祭にボートを出す方法の個数を $10^9+7$ で割った余りを含む．

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

小課題 1（9 分）：$1 \le N \le 500$ を満たし，かつ，全ての $1 \le i \le N$ に対して $a_i=b_i$ を満たす．

小課題 2（22 分）：$1 \le N \le 500$ を満たし，かつ，$\sum_{i=1}^{N}(b_i-a_i) \le 10^6$ を満たす．

小課題 3（27 分）：$1 \le N \le 100$ を満たす．

小課題 4（42 分）：$1 \le N \le 500$ を満たす．