Problem Background

hdkk is making a necklace.

Problem Description

hdkk has $n$ types of beads, each type having $a_i$ beads. He can choose any number of beads to string into a necklace.

Each type of bead has a beauty value $v_i$. hdkk believes that a necklace has a beauty degree. If the $i$-th type of bead appears $cnt$ times in the necklace and $\ge 1$, the beauty degree of the necklace will be increased by $(v_i)^{cnt}$.

Now, he wants to know the total beauty degree of all different necklaces. Please calculate the answer and take the modulo of $10^9+7$.

Two necklaces are considered different if and only if there exists a bead that appears in one necklace but not in the other.

Note: Each bead is unique, even if they are of the same color.

Input Format

The first line contains one positive integer $n$.

The second line contains $n$ integers, where the $i$-th number represents $a_i$.

The third line contains $n$ integers, where the $i$-th number represents $v_i$.

Output Format

One integer, the total beauty degree of all different necklaces modulo $10^9+7$.

Sample Input and Output

Sample Input #1

2
1 2
2 3

Sample Output #1

38

Sample Input #2

2
18 2
9 1

Sample Output #2

786624

Notes

Sample Explanation #1

Color 1: $\{1\}$, Color 2: $\{2, 3\}$.

There are 7 different necklaces: $\{1\}$, $\{2\}$, $\{3\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$, $\{1, 2, 3\}$. The total beauty degree is $2 + 3 + 3 + (2 + 3) + (2 + 3) + 3^2 + (2 + 3^2) = 38$.

This problem uses bundled test cases.

For all data, it is guaranteed that $1 \le n \le 2 \times 10^5$, $1 \le a_i \le 10^9$, $1 \le v_i \le 10^9$.

见题面 Input 部分

见题面 Output 部分