Mixing Drinks and Variance

In a small shop there are (n) regular customers. The (i)-th customer arrives with a bottle of base liquor having a flavor value (a_i) and a condiment having a flavor value (b_i). When mixing a bottle with flavor (x) and a condiment with flavor (y), the resulting drink has flavor (\gcd(x,y)) (note that a lower flavor value means a better taste).

On a particular day, all customers come at the same time and ask for a drink. However, due to the mix‐up from the bartender, the condiments are added to the wrong bottles. Regardless, the customers only care about one thing: they want to know, under all possible ways of mistakenly pairing the condiments with the bottles (i.e. over all permutations (p) of ({1,2,\dots,n})), what is the sum of the variances of the resulting drinks’ flavor values -- computed modulo (10^9+7).

For a permutation (p), let (c_i=\gcd(a_i,b_{p_i})) for (1\le i\le n). The variance (\sigma(c)) of the sequence (c=(c_1,c_2,\dots,c_n)) is defined by

[ \sigma(c)=\frac{1}{n}\sum_{i=1}^{n} c_i^2-\Biggl(\frac{1}{n}\sum_{i=1}^{n} c_i\Biggr)^2. ]

Your task is to compute [ \sum_{p ;\text{is permutation}} \sigma(c) \pmod{10^9+7}. ]

inputFormat

The first line contains a single integer \(n\) (the number of customers).
The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\) separated by spaces.
The third line contains \(n\) integers \(b_1,b_2,\dots,b_n\) separated by spaces.

outputFormat

Output a single integer: the sum of the variances, taken modulo \(10^9+7\).

sample

1
10
20

0