#1646. 奇妙数论题

奇妙数论题

题目描述

ZZ 在学习数论的时候想到一个这样的问题。

给你一个长为 nn排列 aa ,求

i=1nj=1n(ai,aj)\sum_{i = 1}^{n} \sum_{j = 1}^{n} (a_i, a_j)

注意 (ai,aj)(a_i, a_j) 表示 gcd(ai,aj)\gcd(a_i, a_j) ,也就是 ai,aja_i, a_j 的最大公约数。

XX 看了一眼,说道这不是道裸题吗,然后把小 ZZ 吊了一顿。

于是小 ZZ 想了想如何加强,于是多加了一个乘数。

给你一个长为 nn排列 aa ,求

$$\sum_{i = 1}^{n} \sum_{j = 1}^{n} (a_i, a_j) \cdot (i, j) $$

XX 又认真看了看,又说“有什么区别”。

ZZ 没有办法加强了,十分无奈地把这题丢了出来给聪明的你做。

输入格式

第一行两个正整数 nn

接下来一行共 nn 个正整数,其中第 ii 个表示 aia_i

输出格式

输出一行一个数,表示答案,对于 109+710^9 + 7 取模。

样例

5
1 4 5 2 3
73

数据范围与提示

保证 n105n \le 10^5aia_i 为一个 排列