Cat Strength Evaluation

In the Forest Conference, there are ( n ) cats with power values ( a_i ). They form a polynomial:

[ x^n + \sum_{i=1}^{n} a_i x^{n-i} = 0 ]

In other words, the polynomial can be written as:

[ x^n + a_1 x^{n-1} + a_2 x^{n-2} + \cdots + a_{n-1} x + a_n = 0 ]

By the Fundamental Theorem of Algebra, this equation has ( n ) complex roots, call them ( x_1, x_2, \dots, x_n ). Using these roots, we define the expression:

[ E = \sum_{i=1}^{n} \left(b_i \times \sum_{1 \le j_1 < j_2 < \cdots < j_i \le n} x_{j_1} x_{j_2} \cdots x_{j_i} \right) ]

Notice that the inner summation is the sum of all products of ( i ) distinct roots. By Vieta's formulas, we know that:

[ \sum_{1 \le j_1 < j_2 < \cdots < j_i \le n} x_{j_1}x_{j_2}\cdots x_{j_i} = (-1)^i a_i ]

Thus, the expression simplifies to:

[ E = \sum_{i=1}^{n} b_i \cdot (-1)^i \cdot a_i ]

Your task is to compute ( E ) modulo (10^9+7). If the result is negative, output ( E + (10^9+7) ). All computations should be performed with modulus ( M = 10^9+7 ).

inputFormat

Input is given in the following format:

• The first line contains an integer ( n ) ((1 \le n \le 10^5)).
• The second line contains ( n ) integers ( a_1, a_2, \dots, a_n ) representing the coefficients of the polynomial.
• The third line contains ( n ) integers ( b_1, b_2, \dots, b_n ).

All integers are separated by spaces.

outputFormat

Output a single integer: the value of ( E = \sum_{i=1}^{n} b_i \cdot (-1)^i \cdot a_i ) modulo (10^9+7). Note that if the computed value is negative, you must add (10^9+7) to obtain a non-negative result.

sample

1
10
20

999999807