プログラミングコンテストにおいて、ビーバーは問題を最初から最後へと順番に解いていきます。一方、Revaeb（リバーブ）は特殊な齧歯類で、問題を最後から最初へと逆順に解いていきます。

$N$ 匹のビーバーと $N$ 匹のリバーブが、今度のプログラミングコンテストで競い合います！コンテストは $N$ 問の問題で構成されており、$k$ 番目の問題の配点 $p_k$ は $l_k$ 以上 $r_k$ 以下の整数です。参加者のスコアは、その参加者が解いた問題の配点の合計です。

コンテスト当日、$i$ 番目のビーバーは最初の $i$ 問を解き、$j$ 番目のリバーブは最後の $j$ 問を解いたことが分かっています。さらに、同じスコアを持つ参加者のペアは、すべての問題を解いた $N$ 番目のビーバーと $N$ 番目のリバーブのペアのみであることが分かっています。この情報が与えられたとき、コンテストにおける問題の配点の割り当てとして考えられるものの数を数え上げてください。この数は非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。

入力

1行目に問題数 $N$ ($1 \leq N \leq 50$) が与えられます。

続く $N$ 行には、$k$ 番目の問題の配点の範囲 $l_k$ と $r_k$ ($1 \le l_k \le r_k \le 2000$) が空白区切りで与えられます。

出力

配点の割り当てとして考えられる数列の数を $10^9 + 7$ で割った余りを1行で出力してください。

小課題

• ($10$ 点) $N \leq 8$ かつすべての $k$ について $r_k \leq 8$。
• ($30$ 点) すべての $k$ について $l_k = 1$ であり、すべての $k$ について $r_k = R$ となる固定の $R$ が存在する。
• ($30$ 点) すべての $k$ について $r_k \leq 100$。
• ($30$ 点) 追加の制約なし。

入出力例

入力 1

4
1 1
2 2
3 3
10 10

出力 1

1

入力 2

1
1 2000

出力 2

2000

入力 3

4
1 2
1 2
1 2
1 2

出力 3

2

入力 4

5
1 3
2 4
1 4
1 2
3 3

出力 4

18

入力 5

6
1 5
1 5
1 5
1 5
1 5
1 5

出力 5

5120

注記

入出力例 1 の解説

問題の配点は $1, 2, 3, 10$ となるしかありません。この配点を用いると、ビーバーのスコアはそれぞれ $1, 3, 6, 16$ となり、リバーブのスコアはそれぞれ $10, 13, 15, 16$ となります。$4$ 番目のビーバーとリバーブが獲得した $16$ 点を除いて、これらはすべて異なります。したがって、この1つの数列のみが有効であり、答えは $1$ となります。

入出力例 2 の解説

このサンプルは第2小課題の制約を満たしています。

入出力例 3 の解説

このサンプルは第2小課題の制約を満たしています。

有効な配点の数列は $1, 2, 2, 2$ と $2, 2, 2, 1$ のみであり、答えは $2$ となります。

入出力例 5 の解説

このサンプルは第2小課題の制約を満たしています。