题目背景

每当月圆时分，五个族群的族猫们都会聚集在小岛上，进行每月的森林大会。蒟星为了了解其它五族猫的特点，就扮成了一只独行猫来到小岛上……

题目描述

森林大会上有 $n$ 只猫，每只猫的武力值为 $a_i$，于是蒟星列出了下面这样一个方程：

$$x^n+\sum_{i=1}^{n}a_ix^{n-i}=0$$

• 通俗地讲，这个方程就是 $x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-1}x+a_n=0$。

蒟星根据 TA 优（cu）秀（bi）的数学知识可以知道，这个方程在复数集内有 $n$ 个根，不妨把这 $n$ 个根设为 $x_1, x_2, ..., x_n$。

接下来蒟星想要知道森林大会上的猫的实力如何，于是列出了下面一个表达式：

$$\sum_{i=1}^{n}(b_i\times \sum_{1\le j_1 < j_2 <\cdots< j_i \le n}^{n}x_{j_1}x_{j_2}\cdots x_{j_i}) $$

• $\sum_{1\le j_1 < j_2 < \cdots < j_i \le n}^{n}x_{j_1}x_{j_2}\cdots x_{j_i}$ 就是从方程的 $n$ 个根中选出 $i$ 个，求所有可能方案的 $i$ 个根的乘积之和。

但蒟星只要这个表达式对 $10^9+7$ 取模后的值就好了。

• 若答案为负数 $a$，请输出 $a + (10^9+7)$。

蒟星把这个任务交给了您，不过他已经告诉你了 $n$，$a_i$ 和 $b_i$，您能帮帮 TA 吗？

输入格式

第一行一个整数 $n$ —— 表示方程的次数。

第二行 $n$ 个整数 $a_1, a_2, ... a_n$ —— 意义见题目描述。

第三行 $n$ 个整数 $b_1, b_2, ... b_n$ —— 同上。

输出格式

输出一行，一个数，表示这个表达式对 $10^9+7$ 取模后的值。

2
-2 1
1 1

3

3
-3 0 4
2 3 4

999999997

提示

【样例 $1$ 说明】

原方程为 $x^2-2x+1=0$，此时 $x_1=x_2=1$。

表达式的值为 $x_1+x_2+x_1x_2=1+1+1=3$。

【样例 $2$ 说明】

原方程为 $x^3-3x^2+4=0$，此时 $x_1=-1,x_2=x_3=2$。

表达式的值为

$$\begin{aligned}&2\cdot (x_1+x_2+x_3)+3\cdot(x_1x_2+x_1x_3+x_2x_3)+4\cdot x_1x_2x_3\\=\ &2\times(-1+2+2)+3\times(-2+(-2)+4)+4\times (-4)\\=\ &-10\end{aligned} $$

因为 $-10$ 为负数，所以输出 $-10+(10^9+7)=999999997$。

【数据范围与约定】

对于 $10\%$ 的数据，$n=1$。

对于另外 $20\%$ 的数据，$n=2$。

对于 $40\%$ 的数据，$n\leq 10$。

对于 $60\%$ 的数据，$n\leq 10^3$。

对于 $100\%$ 的数据，$1\leq n \le 2 \times 10^5$，$-10^9 \le a_i, b_i \le 10^9$。

【Tips】

韦达定理也许会对你有帮助。

【Source】

Sweet Round 04$\ \$C

idea & std：蒟蒻的名字