有 $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$。
求所有排列 $P$ 的 $f(P)$ 之和，对 $10^{9} + 7$ 取模。
输入格式
第一行包含一个整数 $N$（$1 \le N \le 1500$）。
第二行包含 $N$ 个用空格分隔的整数 $x_{1}, x_{2}, \ldots, x_{N}$（$-10^9 \le x_{i} \le 10^{9}$）。
第三行包含 $N$ 个用空格分隔的整数 $a_{1}, a_{2}, \ldots, a_{N}$（$1 \le a_{i} \le 10^{9}$）。
输出格式
输出一个整数，表示所有排列 $P$ 的 $f(P)$ 之和，对 $10^{9} + 7$ 取模后的结果。
子任务
子任务 1（$7$ 分）：所有 $a_i$ 都相等，即对于所有 $i$（$1 \le i \le n$），$a_i = a_1$
子任务 2（$8$ 分）：$N \le 9$，$-2000 \le x_i,,a_i \le 2000$
子任务 3（$31$ 分）：$N \le 300$，$-10^5 \le x_i,,a_i \le 10^5$
子任务 4（$17$ 分）：$N \le 300$
子任务 5（$25$ 分）：$-10^5 \le x_i,,a_i \le 10^5$
子任务 6（$12$ 分）：无额外限制
样例数据
输入 1
3 2 6 15 1 2 4
输出 1
78
输入 2
1 1 7
输出 2
14
输入 3
4 7 2 7 2 3 2 1 2
输出 3
240
输入 4
7 1 1 2 9 17 26 30 4 4 4 4 4 4 4
输出 4
181440
输入 5
11 257869734 -413759255 671386528 312442221 -479133479 837936940 -775252592 -785229024 -306462979 685409332 62181930 987323333 202379759 242380132 464003610 240120482 288801746 7692451 552912477 795257073 629515685 667287542
输出 5
862900292
输入 6
9 0 0 -2000 396 727 999 999 1300 2000 26 268 268 396 561 604 883 998 999
输出 6
616426169
说明
样例 1：长度为 $3$ 的排列共有 $3! = 6$ 个。设 $p$ 为该排列。
- $p = (1, 2, 3)$：线段分别为 $[1,3]$、$[4,8]$、$[11,19]$，总长度 $= 14$。
- $p = (1, 3, 2)$：线段分别为 $[1,3]$、$[2,10]$、$[13,17]$，总长度 $= 13$。
- $p = (2, 1, 3)$：线段分别为 $[0,4]$、$[5,7]$、$[11,19]$，总长度 $= 14$。
- $p = (2, 3, 1)$：线段分别为 $[0,4]$、$[2,10]$、$[14,16]$，总长度 $= 12$。
- $p = (3, 1, 2)$：线段分别为 $[-2,6]$、$[5,7]$、$[13,17]$，总长度 $= 13$。
- $p = (3, 2, 1)$：线段分别为 $[-2,6]$、$[4,8]$、$[14,16]$，总长度 $= 12$。
答案为 $14 + 13 + 14 + 12 + 13 + 12 = 78$。
样例 2：只有一个排列，且唯一的线段是 $[-6, 8]$。答案为 $8 - (-6) = 14$。
样例 3：注意，可能会有重复的值。不同的排列可能会产生相同的 $a$ 序列，但你仍然需要将它们分别计数（视为不同的排列）。
样例 4：该样例满足子任务 1 的限制。
样例 5：请记得对答案输出 $10^9 + 7$ 取模后的结果。