Description

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 then defined as the total length of black segments on the number line. For example, if $[1, 3], [2, 4], [6, 7]$ is colored black, then the total length of 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 Format

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

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

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

Output Format

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

3
2 6 15
1 2 4

78

1
1
7

14

4
7 2 7 2
3 2 1 2

240

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

181440

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

862900292

9
0 0 -2000 396 727 999 999 1300 2000
26 268 268 396 561 604 883 998 999

616426169

Hint

Note

Sample 1: There are $3! = 6$ permutations of length 3. Let $p$ be the permutation.

• $p = (1, 2, 3)$: the segments are $[1,3]$, $[4,8]$, $[11,19]$, total length = $14$.
• $p = (1, 3, 2)$: the segments are $[1,3]$, $[2,10]$, $[13,17]$, total length = $13$.
• $p = (2, 1, 3)$: the segments are $[0,4]$, $[5,7]$, $[11,19]$, total length = $14$.
• $p = (2, 3, 1)$: the segments are $[0,4]$, $[2,10]$, $[14,16]$, total length = $12$.
• $p = (3, 1, 2)$: the segments are $[-2,6]$, $[5,7]$, $[13,17]$, total length = $13$.
• $p = (3, 2, 1)$: the segments are $[-2,6]$, $[4,8]$, $[14,16]$, total length = $12$.

The answer is $14 + 13 + 14 + 12 + 13 + 12 = 78$.

Sample 2: There is only one permutation, and the only segment is $[-6, 8]$. The answer is $8 - (-6) = 14$.

Sample 3: Note that there may be duplicate values. Different permutations may create the same $a$ sequence, and you should still count them multiple times (as though as they are different).

Sample 4: This fits the constraints of Subtask 1.

Sample 5: Remember to output the answer modulo $10^9 + 7$.

Scoring

Subtask 1 ($7$ points): All $a_i$ are equal, i.e. $a_i = a_1$ for all $i$ ($1 \le i \le n$)

Subtask 2 ($8$ points): $N \le 9$, $-2000 \le x_i,\,a_i \le 2000$

Subtask 3 ($31$ points): $N \le 300$, $-10^5 \le x_i,\,a_i \le 10^5$

Subtask 4 ($17$ points): $N \le 300$

Subtask 5 ($25$ points): $-10^5 \le x_i,\,a_i \le 10^5$

Subtask 6 ($12$ points): No additional constraints