You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $n$ 个整数 $x_1, x_2, \dots , x_n$，

另外还有 $n$ 个正整数 $a_1, a_2, \dots , a_n$。

令排列 $P=(p_1,p_2,\dots , p_n)$ 。

初始，整条数轴都是白色的。

对于每个 $i$，给线段 [$x_i-a_{p_i}, x_i+a_{p_i}$]染成黑色。

如染色线段为 [1,3], [2,4], [6,7] 那么黑色长度为 $4-1+7-6=4$。

令 $f(P)$ 为黑色的总长度。

对于每个排列 $P$，求出 $f(P)$ 之和。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $x_i$。

第三行 $n$ 个整数 $a_i$。

输出格式

输出一个整数，表示 $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\le n \le 1500, -10^9\le x_i \le 10^9 , 1\le a_i \le 10^9$。

子任务1（7分）： 所有 $a_i$ 相同。

子任务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分）：