구간 합집합

$N$개의 양의 정수 $x_{1}, x_{2}, \ldots, x_{N}$과 또 다른 $N$개의 양의 정수 $a_{1}, a_{2}, \ldots, a_{N}$이 주어진다.

$P = (p_{1}, p_{2}, \ldots, p_{N})$을 $\{1, 2, \ldots, N\}$의 순열이라고 하자. 처음에는 수직선 전체가 흰색이다. 각 $1 \le i \le N$에 대해 구간 $[x_{i} - a_{p_{i}}, x_{i} + a_{p_{i}}]$를 검은색으로 칠한다. $f(P)$는 수직선 위에서 검은색으로 칠해진 구간의 전체 길이이다. 예를 들어 $[1, 3]$, $[2, 4]$, $[6, 7]$이 검은색으로 칠해졌다면 검은색 구간의 전체 길이는 $4 - 1 + 7 - 6 = 4$이다.

$\{1, 2, \ldots, N\}$의 모든 순열 $P$에 대한 $f(P)$의 합을 $10^{9} + 7$로 나눈 나머지를 구하라.

첫째 줄에 정수 $N$($1 \le N \le 1500$)이 주어진다.

둘째 줄에 공백으로 구분된 정수 $x_{1}, x_{2}, \ldots, x_{N}$($-10^{9} \le x_{i} \le 10^{9}$)이 주어진다.

셋째 줄에 공백으로 구분된 정수 $a_{1}, a_{2}, \ldots, a_{N}$($1 \le a_{i} \le 10^{9}$)이 주어진다.

모든 순열 $P$에 대한 $f(P)$의 합을 $10^{9} + 7$로 나눈 나머지를 한 개의 정수로 출력한다.

같은 값이 여러 번 나올 수 있다. 같은 $a$ 수열을 만드는 서로 다른 순열도 각각 따로 센다.

답은 $10^{9} + 7$로 나눈 나머지로 출력한다.