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.

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.

Constraints

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

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

见题面 Input 部分

见题面 Output 部分