Migrated from Lutece 1697 简单GCD问题（一）

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

秦队长给你两个长度为$n$的序列$A$和$B$，第$i$个数分别为$a_{i}$和$b_{i}$
请你求出$\sum_{1 \leq i,j \leq n} \gcd \left ( i,j \right ) a_{i} b_{j}$的值
答案可能很大，请输出模$10^9+7$后的结果

Input

第一行输入一个数$n\left ( 1\leq n\leq 100000 \right )$,表示序列长度
第二行输入$n$个数，表示序列$A$，第$i$个数表示$a_{i}\left ( 1\leq a_{i}\leq 1000000 \right )$
第三行输入$n$个数，表示序列$B$，第$i$个数表示$b_{i}\left ( 1\leq b_{i}\leq 1000000 \right )$

Output

输出模$10^9+7$后的答案

Samples

4
1 2 3 4
1 2 3 4

186

Resources

missever