You are given n fractions \frac{a_{1}}{b_{1}}, \frac{a_{2}}{b_{2}}, \dots, \frac{a_{n}}{b_{n}}. What is their sum?

It can be shown that the result can be represented as a fraction p / q, where gcd(p, q) = 1 and q \text{ mod } 10^{9} + 7 \neq 0. Output p \cdot q^{-1} \text{ mod } 10^{9} + 7, where q^{-1} is the modular inverse of q mod 10^{9} + 7, that is, the unique integer such that q \cdot q^{-1} = 1 \text{ mod } 10^{9} + 7.

Input

The first line of input contains the integer n: The number of fractions.

The second line contains the n integers a_{1}, \dots, a_{n}.

The third line contains the n integers b_{1}, \dots, b_{n}.

Output

Output p \cdot q^{-1} \text{ mod } 10^{9} + 7.

Constraints

• 1 \leq n \leq 10^{5}
• 1 \leq a_{i}, b_{i} \leq 10^{9} for all 1 \leq i \leq n

Example

Input:

1
2
3

Output:

666666672

Input:

2
1 500000000
2 7

Output:

0

Explanation:

In the first case, the sum is \frac{2}{3}. The modular inverse of 3 is 333333336, so the result is 2 \cdot 333333336 \text{ mod } 10^{9} + 7 = 666666672.

In thee second case, the sum is \frac{1}{2} + \frac{5 \cdot 10^{8}}{7} = \frac{10^{9} + 7}{14}, so p \cdot q^{-1} \text{ mod } 10^{9} + 7 = 0.