← 返回题目列表

AtCoder · hhkb2020_f

F. 随机最大值

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 连续随机变量 x_i (1 ≤ i ≤ N),每个都遵循区间上的连续均匀分布 [L_i, R_i]。 (也就是说, x_i 是一个随机变量,可以取介于 L_i 和 R_i (含)等概率。)

让 E 是这些最大值的期望值 N 随机变量。在本问题的约束下,可以证明 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