[FesdrerOI R6, T2] 永远的方神

题目描述

有 $n$ 个方排成一列，第 $i$ 个方有两个参数 $A _ i, B _ i$。

一个方的权值 $C _ i$ 定义为排在它前面的方和自己的 $A _ i$ 之和乘上自己的 $B _ i$，即 $C _ i = B _ i \sum \limits _ {j = 1} ^ i A _ j$。

你需要重新排列这 $n$ 个方，使它们权值之和最大化。由于权值之和可能很大，你只需输出答案对 $10 ^ 9 + 7$ 取模后的数就可以了。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $A _ 1, A _ 2, \ldots, A _ n$。

第三行 $n$ 个正整数 $B _ 1, B _ 2, \ldots, B _ n$。

输出格式

一个整数，表示这些方权值之和的最大值，对 $10 ^ 9 + 7$ 取模。

样例 #1

样例输入 #1

4
1 2 3 3 
2 1 4 3

样例输出 #1

67

样例 #2

样例输入 #2

6
1 1 4 5 1 4 
1 9 1 9 8 10

样例输出 #2

503

样例 #3

样例输入 #3

2
114514 191981 
191981 114514

样例输出 #3

825728269

提示

样例 #1 解释

我们按照原来第 $2, 4, 3, 1$ 个的顺序重排，重排后 $A = [2, 3, 3, 1]$，$B = [1, 3, 4, 2]$，$C = [2, 15, 32, 18]$，和为 $67$。可以证明没有比这更大的方案。

数据范围

对于 $20 \%$ 的数据，$1 \le n \le 8$。

对于 $40 \%$ 的数据，$1 \le n \le 16$。

对于另外 $15 \%$ 的数据，$A _ i = 1$。

对于另外 $15 \%$ 的数据，$B _ i = 1$。

对于 $100 \%$ 的数据，$1 \le n \le 5 \times 10 ^ 5$，$1 \le A _ i, B _ i \le 10 ^ 9$。