Problem Background

Syzygy, translated as "朔望" in Chinese, refers to the alignment of three or more celestial bodies approximately in a straight line. This problem primarily explores the scenario where a parent star and at least two planets are aligned.

Problem Description

In an ideal planetary system, all planets orbit a single common parent star in uniform circular motion within the same plane and in the same direction (e.g., counterclockwise). We define the Syzygy index of such a planetary system as the sum of the rarity of all syzygies (including the parent star) that occur annually. The rarity of a single syzygy is a constant \( w_x \) related to the number of planets \( x \) involved in the alignment. If multiple syzygies occur simultaneously 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 innermost) has an orbital period of \( t_i \) years (according to Kepler's Third Law, \( t_i \) is monotonically increasing). Suppose there exists a moment when all \( n \) planets are on a ray with the parent star as its endpoint. Calculate the Syzygy index of this system.

Input Format

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, \ldots, t_n \), representing the orbital periods of the planets from the innermost to the outermost. 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, \ldots, w_n \) (\( 1 \le w_i \le 10^9 \)), representing the rarity of syzygies involving different numbers of planets.

Output Format

Output the Syzygy index of the planetary system. Clearly, the Syzygy index is a rational number; assume it is in its simplest fractional form \( 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 within the scope of this problem, \( x \) exists and is unique.

Sample Input and Output

Sample Input #1

2
3 4
5

Sample Output #1

833333340

Sample Input #2

3
4 5 6
7 8

Sample Output #2

300000004

Sample Input #3

4
4 6 8 24
20 22 1207

Sample Output #3

250000119

Sample Input #4

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

Sample Output #4

94380764

Notes

Sample Explanation 1

Assume at time \( T=0 \), the two planets are on the same ray with the parent star as its endpoint. Since the least common multiple of the orbital periods of the two planets is 12 years, and the synodic period of the two planets is also exactly \( \frac{1}{\left|\frac{1}{3} - \frac{1}{4}\right|} = 12 \) years, we can consider the planetary system's motion within \( T \in [0, 12) \) years. When \( T \) takes integer values within \( [0, 12) \), the planetary system's motion is as shown in the following diagrams:

[Image: 1.png]

It can be proven that within a 12-year cycle, the two planets only experience 2 syzygies as shown in the diagrams (one at \( T=0 \) and one at \( T=6 \)). Therefore, the Syzygy index of this planetary system is

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

Sample Explanation 2

Similarly, assume at time \( T=0 \), the three planets are on the same ray with the parent star as its endpoint. Since \( \text{lcm}(4, 5, 6) = 60 \), we can consider the planetary system's motion within \( T \in [0, 60) \) years. All syzygies involving the parent star within this period are shown in the following diagrams:

[Image: 2.png]

Therefore, the Syzygy index of this planetary system is

\[ \frac{14 \times 7 + 2 \times 8}{60} = \frac{19}{10} \equiv 300000004 \pmod{10^9 + 7}. \]

Sample Explanation 3

Similarly, assume at time \( T=0 \), the four planets are on the same ray with the parent star as its endpoint. Since \( \text{lcm}(4, 6, 8, 24) = 24 \), we can consider the planetary system's motion within \( T \in [0, 24) \) years. All syzygies involving the parent star within this period are shown in the following diagrams:

[Image: 3.png]

Therefore, the Syzygy index of this planetary system is

\[ \frac{20 \times 20 + 0 \times 22 + 2 \times 1207}{24} = \frac{1407}{12} \equiv 250000119 \pmod{10^9 + 7}. \]

Source and Acknowledgements

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

For data, problem statements, standard solutions, and problem explanations, please refer to the THUPC official repository at https://thusaac.com/public

见题面 Input 部分

见题面 Output 部分