Description

At the forest meeting there are $n$ cats, and the strength value of each cat is $a_i$. So Juxing wrote down the following equation:

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

• In plain words, this equation is $x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-1}x+a_n=0$.

With their excellent (cu) math skills, Juxing knows that this equation has $n$ roots in the complex numbers. Let these $n$ roots be $x_1, x_2, ..., x_n$.

Next, Juxing wants to know how strong the cats at the forest meeting are, so they wrote the following expression:

$$\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}$ means: choose $i$ roots from the $n$ roots of the equation, and sum the products of the chosen $i$ roots over all possible choices.

But Juxing only needs the value of this expression modulo $10^9+7$.

• If the answer is a negative number $a$, please output $a + (10^9+7)$.

Juxing gives this task to you. They have already told you $n$, $a_i$, and $b_i. Can you help them?

Input Format

The first line contains an integer $n$ — the degree of the equation.

The second line contains $n$ integers $a_1, a_2, ... a_n$ — as described in the statement.

The third line contains $n$ integers $b_1, b_2, ... b_n$ — same as above.

Output Format

Output one line containing one number, the value of this expression modulo $10^9+7$.

2
-2 1
1 1

3

3
-3 0 4
2 3 4

999999997

Hint

Sample 1 Explanation:

The original equation is $x^2-2x+1=0$, and $x_1=x_2=1$.

The value of the expression is $x_1+x_2+x_1x_2=1+1+1=3$.

Sample 2 Explanation:

The original equation is $x^3-3x^2+4=0$, and $x_1=-1,x_2=x_3=2$.

The value of the expression is

$$\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}$$

Since $-10$ is negative, output $-10+(10^9+7)=999999997$.

Constraints:

For $10\%$ of the testdata, $n=1$.

For another $20\%$ of the testdata, $n=2$.

For $40\%$ of the testdata, $n\leq 10$.

For $60\%$ of the testdata, $n\leq 10^3$.

For $100\%$ of the testdata, $1\leq n \le 2 \times 10^5$, $-10^9 \le a_i, b_i \le 10^9$.

Tips:

Vieta's formulas may be helpful.

Source:

Sweet Round 04$\ \$C

idea & std: 蒟蒻的名字

Translated by ChatGPT 5