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