Background

Syzygy, translated into Chinese as 朔望, means that three or more celestial bodies are roughly on the same straight line. This problem mainly discusses the case where the parent star and at least two planets are on the same straight line.

Problem Description

In an ideal planetary system, all planets move in uniform circular orbits around a single common parent star in the same plane, and all orbit in the same direction (for example, all counterclockwise). We define the Syzygy index of such a planetary system as the sum, over all syzygies (including the parent star) occurring on average per year, of their rarity. The rarity of a single syzygy is a constant $w_x$ that depends on the number of planets $x$ that form the line. If multiple syzygies happen at the same time in the system but they are not on the same straight line, then the rarity is counted separately for the planets on each line.

Now consider an ideal planetary system with $n$ planets. From inner to outer, the orbital period of the $i$-th planet around the parent star is $t_i$ years (by Kepler's third law, $t_i$ is strictly increasing). Assume that at some moment, all $n$ planets lie on the same ray with the parent star as an endpoint. Compute the Syzygy index of this system.

Input Format

The first line contains a positive integer $n$ ($2\le n\le 20$), the number of planets in this 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 inner to outer. 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 a syzygy involving different numbers of planets.

Output Format

Output the Syzygy index of this planetary system. Obviously, the Syzygy index is a rational number. Suppose it is reduced to the simplest fraction $p/q$ (i.e. $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 constraints of this problem, $x$ exists and is unique.

2
3 4
5

833333340

3
4 5 6
7 8

300000004

4
4 6 8 24
20 22 1207

250000119

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

94380764

Hint

Sample Explanation 1

Assume that at time $T=0$, two planets lie on the same ray with the parent star as an endpoint. Since the least common multiple of the two orbital periods is $12$ years, and their synodic period is also exactly $\displaystyle\frac{1}{\displaystyle\left|\frac{1}{3}-\frac{1}{4}\right|}=12$ years, we can take the system’s evolution over $T\in[0, 12)$ years as the object of study. When $T$ takes integer values in $[0, 12)$, the system’s states are shown in the figures below:

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

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

Sample Explanation 2

Similarly, assume that at time $T=0$, three planets lie on the same ray with the parent star as an endpoint. Since $\mathrm{lcm}(4, 5, 6)=60$, we can take the system’s evolution over $T\in[0,60)$ years as the object of study. During this interval, all syzygies involving the parent star are shown in the figure below:

Therefore, the Syzygy index of this system is

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

Sample Explanation 3

Similarly, assume that at time $T=0$, four planets lie on the same ray with the parent star as an endpoint. Since $\mathrm{lcm}(4, 6, 8, 24)=24$, we can take the system’s evolution over $T\in[0,24)$ years as the object of study. During this interval, all syzygies involving the parent star are shown in the figure below:

Therefore, the Syzygy index of this system is

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

Source and Acknowledgements

From the THUPC2024 (2024 Tsinghua University Student Programming Contest and Invitational Contest) finals. Thanks to THUSAA for providing the problem.

For the testdata, statement, reference solution, editorial, etc., please refer to the THUPC official repository https://thusaac.com/public.

Translated by ChatGPT 5