Background

hdkk is making a necklace.

Problem Description

hdkk has $n$ colors of beads. For the $i$-th color, there are $a_i$ beads. He can choose any number of beads and string them into a necklace.

Each color has a beauty value $v_i$. hdkk defines a “beauty score” for a necklace: if the $i$-th color appears $cnt$ times in the necklace and $cnt \ge 1$, then the beauty score of this necklace increases by $(v_i)^{cnt}$.

Now he wants to know the sum of beauty scores over all different necklaces. Please compute the answer modulo $10^9+7$.

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

Note that every bead is distinct, even if they have the same color.

Input Format

Line $1$ contains one positive integer $n$.

Line $2$ contains $n$ integers, where the $i$-th number is $a_i$.

Line $3$ contains $n$ integers, where the $i$-th number is $v_i$.

Output Format

Output one integer: the sum of beauty scores of all different necklaces modulo $10^9+7$.

2
1 2
2 3 

38

2
18 2
9 1

786624

Hint

Sample Explanation #1

Color $1$: $\left\{1\right\}$, color $2$: $\left\{2,3\right\}$.

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

This problem uses bundled testdata.

For all testdata, it is guaranteed that $1\le n\le2\times10^5$, $1\le a_i\le10^9$, and $1\le v_i\le10^9$.

Translated by ChatGPT 5