問題文

$N$ 個の連続型確率変数 $x_i$ ($1 ≤ i ≤ N$) があり、それぞれ \[L_i, R_i\] の範囲をとる連続一様分布にしたがいます。 (すなわち、$x_i$ は $L_i$ 以上 $R_i$ 以下の実数を等確率でとりうるランダムな変数です)

本問題の制約下では、これらの $N$ 個の確率変数の最大値の期待値を $E$ とすると、$E \\times (N+1)! \\times \\prod_{i=1}^N (R_i - L_i)$ は正整数であることが示せます。この値を $1,000,000,007$ で割ったあまりを求めてください。

制約

• $1 ≤ N ≤ 1000$
• $0 ≤ L_i < R_i ≤ 10^9$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $L_1$ $R_1$ $:$ $L_N$ $R_N$

出力

$E \\times (N+1)! \\times \\prod_{i=1}^N (R_i - L_i)$ を $1,000,000,007$ で割ったあまりを整数で出力せよ。

入力例 1

1
1 2

出力例 1

3

この確率変数の最大値の期待値は、とりうる範囲の中央値、すなわち $E = \\frac{3}{2}$ に等しいです。

よって、 $E \\times (N+1)! \\times (R_1 - L_1) = E \\times 2 = 3$ が正解となります。

入力例 2

2
1 2
1 2

出力例 2

10

求める期待値は $E = \\frac{5}{3}$ です。

入力例 3

2
1 2
2 4

出力例 3

36

入力例 4

5
40 96
81 92
16 384
32 768
65 536

出力例 4

52776507