题目描述

淮如，淮如，秦淮如...

淮如姑娘的思想貌似不像古人，她正在思考一道比较困难的数学题，虾仁凑近一看：

这里有一串长度为 $n$ 的序列，序列中的每个值为 $a_i$，请计算：

$$\sum_{i=1}^n \sum_{j=i+1}^n \sum_{k=j+1}^n f(a_i,a_j,a_k)^\dagger $$

为了得到淮如姑娘的芳心，虾仁决定帮帮淮如姑娘解决这个比较简单的问题。

$^\dagger$ 将 $x,y,z$ 升序为 $x \leq y \leq z$ ，$f(x,y,z)=\text{lcm}(x,y)$ ，$\text{lcm}(x,y)$ 表示 $x$ 和 $y$ 的最小公倍数。

输入格式

第一行包含一个整数 $n\ \left(3 \le n \le 10^5\right)$ 表示序列的长度。

第二行包含 $n$ 个正整数 $a_i\ \left(1 \le a_i \le 10^5\right)$ 表示序列的每个元素。

输出格式

输出一个数字，即淮如姑娘思考的问题答案，对 $10^9+7$ 取模。

样例输入1

4
2 4 3 6

样例输出1

28

样例输入2

10
10 19 11 19 7 5 10 1 18 8

样例输出2

6219

样例解释

无