说明

给定 $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$）。

输入的第二行包含 $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}$）。

输出格式

输出一个整数，表示所有 $\{1, 2, \ldots, N\}$ 的排列 $P$ 的 $f(P)$ 之和，对 $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

提示

注释

样例 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$ 取模后的结果。

计分

子任务 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$ 分）： 无额外限制

翻译由 DeepSeek 完成