P7496 干杯！再会！

>酒酣之时，等待你的会是…… 黛米和哥哥在一个小城镇里经营着一家小酒吧。靠着哥哥调制的多夫林酒，这间小酒吧的生意也逐渐兴隆起来。

这家小店有 $n$ 位常驻顾客。第 $i$ 位顾客来到这家小店时都会带上一瓶美味度为 $a_i$ 的底酒和一份美味度为 $b_i$ 的调料。这些顾客会让黛米帮忙调酒。对于一瓶美味度为 $x$ 的底酒和一份美味度为 $y$ 的调料，如果黛米将它们调制在一起，就能得到一瓶美味度为 $\gcd(x,y)$ 的美酒（我们认为美味度数值越低代表酒越好喝）。 这一天，这些顾客同时来到了这家小店想要黛米帮忙调酒。然而黛米在前一天喝了太多的酒导致意识错乱了，这导致她将调料加入到了错误的底酒里。不过好在这些顾客并不在意，他们只想知道对于**所有**黛米加入调料的情况下，他们将会拿到的酒的美味度的**方差**的**和**在对 $10^9+7$ 取模意义下是多少。如果你能回答出他们的问题，那么他们会很愿意帮你支付酒钱。 ------------ #### 简要题意： 给定 $n$ 以及两个长度为 $n$ 的序列 $a,b$。对于一个 $1$ 到 $n$ 的排列 $p$，记 $c_i=\gcd(a_i,b_{p_i})$，$\sigma(c)$ 表示序列 $c$ 中所有元素的**方差**（方差公式详见提示），求： $$\sum\limits_{p}\sigma(c)$$ 对 $10^9+7$ 取模。

第一行一个整数 $n$，意义如上。 第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。 第三行有 $n$ 个整数，第 $i$ 个整数表示 $b_i$。

一行一个整数，表示答案。

#### 样例一解释 + $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}$。 总和为 $\dfrac{16}{9}$，对 $10^9+7$ 取模意义下为 $777777785$。 ------------ #### 数据范围 **本题采用捆绑测试**。 + 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\%$ )：无特殊限制。 对于所有数据，$2\leq n\leq 10^6,1\leq a_i,b_i\leq 10^6$。 ------------ 对于一个长度为 $n$ 的序列 $x$，方差 $\sigma(x)=\sum\limits_{i=1}^n\dfrac{1}{n}(x_i-\bar{x})^2$，其中 $\bar{x}$ 表示所有元素的平均数（$\bar{x}=\dfrac{1}{n}\sum\limits_{i=1}^nx_i$）。