Contest Duration: - (local time) (100 minutes) Back to Home
F - Random Max /

Time Limit: 3 sec / Memory Limit: 1024 MB

### 問題文

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

### 制約

• 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


### 入力例 3

2
1 2
2 4


### 出力例 3

36


### 入力例 4

5
40 96
81 92
16 384
32 768
65 536


### 出力例 4

52776507


Score : 600 points

### Problem Statement

There are N continuous random variables x_i (1 ≤ i ≤ N), each of which follows the continuous uniform distribution on the interval [L_i, R_i]. (That is, x_i is a random variable that can take any real value between L_i and R_i (inclusive) with equal probability.)

Let E be the expected value of the maximum of these N random variables. Under the constraints in this problem, it can be proved that E \times (N+1)! \times \prod_{i=1}^N (R_i - L_i) is a positive integer. Find this value modulo 1,000,000,007.

### Constraints

• 1 ≤ N ≤ 1000
• 0 ≤ L_i < R_i ≤ 10^9
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
L_1 R_1
:
L_N R_N


### Output

Print E \times (N+1)! \times \prod_{i=1}^N (R_i - L_i) modulo 1,000,000,007, as an integer.

### Sample Input 1

1
1 2


### Sample Output 1

3


The expected value of the maximum of these random variables - there is actually just one in this case - is equal to the median of the range of the values the variable can take, that is, E = \frac{3}{2}.

Thus, the correct output is E \times (N+1)! \times (R_1 - L_1) = E \times 2 = 3.

### Sample Input 2

2
1 2
1 2


### Sample Output 2

10


The expected value in question is E = \frac{5}{3}.

### Sample Input 3

2
1 2
2 4


### Sample Output 3

36


### Sample Input 4

5
40 96
81 92
16 384
32 768
65 536


### Sample Output 4

52776507