P10185 [YDOI R1] Necklace

hdkk is making a necklace.

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.

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 one integer: the sum of beauty scores of all different necklaces modulo $10^9+7$.

### 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.** |Subtask ID|$n\le$|$a_i\le$|Points| |:--:|:--:|:--:|:--:| |$1$|$4$|$5$|$15$| |$2$|$10^3$|$10^3$|$25$| |$3$|$2\times10^5$|$10^9$|$60$| 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