Segment Union

Time limit5sMemory limit1024 MB

Summary

Given centers x_i and radii a_i, sum the union length of the intervals [x_i - r, x_i + r] over all ways to assign the radii to the centers, modulo 1e9+7.

Level: Hard9 of 10
Topics: Sorting, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

There are $N$ positive integers $x_{1}, x_{2}, \ldots, x_{N}$ and another $N$ positive integers $a_{1}, a_{2}, \ldots, a_{N}$ .

Let $P = (p_{1}, p_{2}, \ldots, p_{N})$ be a permutation of $\{1, 2, \ldots, N\}$ . Initially, the entire number line is white. For each $1 \le i \le N$ , the segment $[x_{i} - a_{p_{i}}, x_{i} + a_{p_{i}}]$ is colored black. $f(P)$ is the total length of the black segments on the number line. For example, if $[1, 3]$ , $[2, 4]$ , and $[6, 7]$ are colored black, the total length of the black segments is $4 - 1 + 7 - 6 = 4$ .

Find the sum of $f(P)$ over all permutations $P$ of $\{1, 2, \ldots, N\}$ , modulo $10^{9} + 7$ .

Input

The first line contains a single integer $N$ ( $1 \le N \le 1500$ ).

The second line contains $N$ space-separated integers $x_{1}, x_{2}, \ldots, x_{N}$ ( $-10^{9} \le x_{i} \le 10^{9}$ ).

The third line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$ ( $1 \le a_{i} \le 10^{9}$ ).

Output

Output a single integer, the sum of $f(P)$ over all permutations $P$ of $\{1, 2, \ldots, N\}$ , modulo $10^{9} + 7$ .

Hint

Values may repeat. Different permutations that produce the same sequence of $a$ values are still counted separately.

Print the answer modulo $10^{9} + 7$ .

Examples5

Example 1
Input
```
3
2 6 15
1 2 4
```
Expected output
```
78
```
Example 2
Input
```
1
1
7
```
Expected output
```
14
```
Example 3
Input
```
4
7 2 7 2
3 2 1 2
```
Expected output
```
240
```

Example 4

Input

7
1 1 2 9 17 26 30
4 4 4 4 4 4 4

Expected output

Example 5

Input

11
257869734 -413759255 671386528 312442221 -479133479 837936940 -775252592 -785229024 -306462979 685409332 62181930
987323333 202379759 242380132 464003610 240120482 288801746 7692451 552912477 795257073 629515685 667287542

Expected output

862900292