P15293 [MCO 2023] Segment Union

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

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 a single integer, the sum of $f(P)$ over all permutations $P$ of $\{1, 2, \ldots, N\}$, modulo $10^{9} + 7$.

### 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