题目描述

有 $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