Description

This small shop has $n$ regular customers. When the $i$-th customer comes to the shop, they bring a base wine with deliciousness $a_i$ and a seasoning with deliciousness $b_i$. These customers ask Demi to mix the wine for them. For a base wine with deliciousness $x$ and a seasoning with deliciousness $y$, if Demi mixes them together, she can obtain a bottle of fine wine with deliciousness $\gcd(x,y)$ (we consider that a lower deliciousness value means the wine tastes better).

On this day, these customers came to the shop at the same time and wanted Demi to mix the wine. However, Demi drank too much the day before and became confused, which caused her to add the seasonings to the wrong base wines. Fortunately, the customers do not mind. They only want to know, for all possible ways Demi adds the seasonings, what the result is of the sum of the variances of the deliciousness values of the wines they will get, taken modulo $10^9+7$. If you can answer their question, they will be very willing to help you pay for the drinks.

Brief statement:

Given $n$ and two sequences $a, b$ of length $n$. For a permutation $p$ of $1$ to $n$, define $c_i=\gcd(a_i,b_{p_i})$. Let $\sigma(c)$ denote the variance of all elements in sequence $c$ (see the variance formula in the hint). Compute:

modulo $10^9+7$.

Input Format

The first line contains an integer $n$, as described above.

The second line contains $n$ integers; the $i$-th integer is $a_i$.

The third line contains $n$ integers; the $i$-th integer is $b_i$.

Output Format

Output one integer on one line, the answer.

3
1 2 3
1 2 3

777777785

12
1 3 4 2 3 5 7 3 5 6 8 9
4 3 10 2 5 6 4 8 2 9 12 5

931089600

Hint

Explanation for Sample 1

• $p=\{1,2,3\},c=\{1,2,3\},\sigma(c)=\dfrac{2}{3}$.
• $p=\{1,3,2\},c=\{1,1,1\},\sigma(c)=0$.
• $p=\{2,1,3\},c=\{1,1,3\},\sigma(c)=\dfrac{8}{9}$.
• $p=\{2,3,1\},c=\{1,1,1\},\sigma(c)=0$.
• $p=\{3,1,2\},c=\{1,1,1\},\sigma(c)=0$.
• $p=\{3,2,1\},c=\{1,2,1\},\sigma(c)=\dfrac{2}{9}$.

The total sum is $\dfrac{16}{9}$, which is $777777785$ modulo $10^9+7$.

Constraints

This problem uses bundled testdata.

• Subtask 1 ( $5\%$ ): $n\leq8$.
• Subtask 2 ( $15\%$ ): $n,a_i,b_i\leq100$.
• Subtask 3 ( $25\%$ ): $a_i,b_i\leq10^3$.
• Subtask 4 ( $25\%$ ): $n,a_i,b_i\leq 10^5$.
• Subtask 5 ( $30\%$ ): no special constraints.

For all testdata: $2\leq n\leq 10^6,1\leq a_i,b_i\leq 10^6$.

For a sequence $x$ of length $n$, the variance is $\sigma(x)=\sum\limits_{i=1}^n\dfrac{1}{n}(x_i-\bar{x})^2$, where $\bar{x}$ is the average of all elements ($\bar{x}=\dfrac{1}{n}\sum\limits_{i=1}^nx_i$).

Translated by ChatGPT 5