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