← 返回题目列表

Codeforces · 1575/G

G. GCD节

中文机器翻译题面 查看原题

Chanek 先生有一个由 $$$n$$$ 整数组成的数组 $$$a$$$。 $$$a$$$ 的漂亮值表示为:

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

其中 $$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

换句话说,数组 $$$a$$$ 的漂亮值是所有 $$$(i, j)$$$ 对的 $$$\gcd(a_i, a_j) \cdot \gcd(i, j)$$$ 的总和。

帮助 Chanek 先生找到 $$$a$$$ 的漂亮值,并输出对 $$$10^9 + 7$$$ 取模的结果!

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$)。

输出

输出一个整数,表示 $$$a$$$ 的漂亮值模 $$$10^9 + 7$$$。

示例

输入 #1

5
3 6 2 1 4

输出 #1

77