Problem Description

给定长度为 $n$ 的正整数序列 $a_1, a_2, ..., a_n$，求：

$$\sum_{i=1}^{n-2} \sum_{j=i+1}^{n-1} \sum_{k=j+1}^{n} \gcd(a_i \times a_j,\ a_j \times a_k,\ a_i \times a_k) \times \operatorname{lcm}(a_i, a_j, a_k)$$

其中 $\gcd(x,y,z)$ 与 $\operatorname{lcm}(x,y,z)$ 分别表示 $x,y,z$ 的最大公约数和最小公倍数。由于答案可能很大，请你输出对 $10^9 + 7$ 取模的结果。

Input Format

第一行一个正整数 $n$（$3 \le n \le 2 \times 10^5$），表示序列长度。

第二行 $n$ 个正整数 $a_1, a_2, ..., a_n$（$1 \le a_i \le 10^9$），以空格分隔。

Output Format

一行一个整数，表示所求结果对 $10^9 + 7$ 取模后的值。

4
1 2 3 4

50