P7496 Cheers! Goodbye!

> When you are drunk, what awaits you is... Demi and her older brother run a small bar in a small town. Thanks to the Dovlin wine mixed by her brother, the business of this little bar has gradually become prosperous.

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: $$\sum\limits_{p}\sigma(c)$$ modulo $10^9+7$.

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 one integer on one line, the answer.

#### 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