Background

Syzygy refers to the configuration where three or more celestial bodies are approximately in a straight line. This problem explores cases where a central star and at least two planets are collinear.

Description

In an ideal planetary system, all planets revolve around a single central star in the same plane, in circular orbits at constant speeds, and in the same direction (e.g., counter-clockwise). We define the Syzygy index of such a planetary system as the sum of the rarity of all syzygies (involving the central star) that occur per year. The rarity of a single syzygy is a constant $w_x$ that depends on the number of planets $x$ forming the line. If multiple syzygies occur simultaneously in the system but are not on the same line, the rarity is calculated separately for each line of planets.

Given an ideal planetary system with $n$ planets, where the $i$-th planet from the inside has an orbital period of $t_i$ years (where $t_i$ is monotonically increasing, consistent with Kepler's Third Law). Assume that at a certain moment, all $n$ planets are located on the same ray originating from the central star. Calculate the Syzygy index of this system.

Input

Read from standard input.

The first line contains a positive integer $n$ ($2\le n\le 20$), representing the number of planets in the single-star system.

The second line contains $n$ positive integers $t_1, t_2, \cdots, t_n$, representing the orbital periods of the planets from the inside out. It is guaranteed that $1\le t_1 < t_2 < \cdots < t_n\le 10^9$.

The third line contains $(n-1)$ positive integers $w_2, w_3, \cdots, w_n$ ($1\le w_i\le 10^9$), representing the rarity of syzygies involving different numbers of planets.

Output

Output to standard output.

Output the Syzygy index of the planetary system. The Syzygy index is clearly a rational number; assume it is expressed as an irreducible fraction $p/q$ (where $p$ and $q$ are coprime). Output $x$ such that $qx\equiv p \pmod{10^9 + 7}$ and $0\le x < 10^9 + 7$. It can be proven that under the given constraints, $x$ exists and is unique.

Examples

Input 1

2
3 4
5

Output 1

833333340

Note 1

Assume that at time $T=0$, both planets are on the same ray originating from the central star. Since the least common multiple of the two orbital periods is $12$ years, and the synodic period of the two planets is exactly $\displaystyle\frac{1}{\displaystyle\left|\frac{1}{3}-\frac{1}{4}\right|}=12$ years, we can study the system's behavior over $T\in[0, 12)$ years. The state of the system for integer values of $T$ in $[0, 12)$ is shown in the figures below:

It can be proven that within the $12$-year cycle, the two planets form a syzygy only $2$ times as shown above (the inner planet transit/outer planet opposition at $T=0$ and the conjunction at $T=6$). Therefore, the Syzygy index of the system is:

$$ \frac{2\times 5}{12} = \frac{5}{6} \equiv 833333340 \pmod{10^9 +7}. $$

Input 2

3
4 5 6
7 8

Output 2

300000004

Note 2

Similarly, assume that at $T=0$, all three planets are on the same ray originating from the central star. Since $\mathrm{lcm}(4, 5, 6)=60$, we can study the system's behavior over $T\in[0, 60)$ years. During this period, all syzygies involving the central star are shown in the figure below:

Therefore, the Syzygy index of the system is:

$$ \frac{14\times 7+2\times 8}{60}=\frac{19}{10}\equiv300000004 \pmod{10^9+7}. $$

Input 3

4
4 6 8 24
20 22 1207

Output 3

250000119

Note 3

Similarly, assume that at $T=0$, all four planets are on the same ray originating from the central star. Since $\mathrm{lcm}(4, 6, 8, 24)=24$, we can study the system's behavior over $T\in[0, 24)$ years. During this period, all syzygies involving the central star are shown in the figure below:

Therefore, the Syzygy index of the system is:

$$ \frac{20\times 20+0\times22+2\times 1207}{24}=\frac{1407}{12}\equiv250000119 \pmod{10^9+7}. $$

Input 4

9
88 225 365 687 4333 10759 30685 60189 90560
306 241 336 406 342 86884 86885 86886

Output 4

94380764