F - Random Max Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

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

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