题目背景

酒酣之时，等待你的会是……

黛米和哥哥在一个小城镇里经营着一家小酒吧。靠着哥哥调制的多夫林酒，这间小酒吧的生意也逐渐兴隆起来。

题目描述

这家小店有 $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$ 中所有元素的方差（方差公式详见提示），求：

对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$，意义如上。

第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

第三行有 $n$ 个整数，第 $i$ 个整数表示 $b_i$。

输出格式

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

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

提示

样例一解释

• $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$）。