Necklace Beauty Sum

hdkk has \( n \) types of beads. For each type \( i \), there are \( a_i \) distinct beads and each bead has an associated beauty value \( v_i \). hdkk can choose an arbitrary number of beads from the available ones to form a necklace.

The beauty of a necklace is defined as follows: for each bead type \( i \), if the necklace contains \( k \) beads of that type (with \( k \ge 1 \)), then the beauty increases by \( v_i^{k} \) (i.e. \( (v_i)^k \)). The overall beauty of the necklace is the sum of contributions from all bead types.

Two necklaces are considered different if there exists at least one bead that appears in one necklace but not in the other. Note that even beads of the same color are distinct.

You are required to compute the sum of the beauties of all possible necklaces modulo \(10^9+7\).

Hint: For each type \( i \), the sum over non-empty selections from its \( a_i \) beads can be computed as:

\[ \sum_{k=1}^{a_i} \binom{a_i}{k} v_i^{k} = (1+v_i)^{a_i} - 1. \]

If the total number of beads is \( T = \sum_{i=1}^n a_i \), then for bead type \( i \) the independent selections from other types contribute a factor of \( 2^{T-a_i} \). Thus, the overall contribution from bead type \( i \) is \( 2^{T-a_i} \cdot \Bigl( (1+v_i)^{a_i} - 1 \Bigr) \).

inputFormat

The input consists of three lines:

• The first line contains an integer \( n \), the number of bead types.
• The second line contains \( n \) space-separated integers \( a_1, a_2, \ldots, a_n \), where \( a_i \) represents the number of beads of type \( i \).
• The third line contains \( n \) space-separated integers \( v_1, v_2, \ldots, v_n \), where \( v_i \) is the beauty value of beads of type \( i \).

outputFormat

Output a single integer: the sum of the beauties of all different necklaces, taken modulo \(10^9+7\).

sample

1
1
2

2