题目描述

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

给你一个长为 $n$ 的 排列 $a$ ，求 $$ \sum{i = 1}^{n} \sum{j = 1}^{n} (a_i, a_j) $$

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

小 $X$ 看了一眼，说道这不是道裸题吗，然后把小 $Z$ 吊了一顿。

于是小 $Z$ 想了想如何加强，于是多加了一个乘数。

给你一个长为 $n$ 的 排列 $a$ ，求

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

小 $X$ 又认真看了看，又说“有什么区别”。

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

输入格式

第一行两个正整数 $n$ 。

接下来一行共 $n$ 个正整数，其中第 $i$ 个表示 $a_i$ 。

输出格式

输出一行一个数，表示答案，对于 $10^9 + 7$ 取模。

样例

input

5
1 4 5 2 3

output

73

数据范围与提示

保证 $n \le 10^5$ 且 $a_i$ 为一个 排列 。