Zadanie

Láska k matematike

Počet bodov: 100, časový limit: 1000ms

Pre celé čísla \(a, b\) definujeme \(\operatorname{lcm}(a, b)\) ako ich najmenší spoločný násobok. Napríklad, \(\operatorname{lcm}(40, 32) = 160\).

Na vstupe dostanete \(N\) celých čísel \(a_1, \dots, a_N\) a máte vypočítať

\[\sum_{1 \le i, j \le N} \operatorname{lcm}(a_i, a_j)\]

Výsledok vypíšte modulo \(10^9+7\).

Vstup a výstup

Na prvom riadku je \(N\), počet čísel (\(1 \le N \le 500\,000\)). Druhý riadok obsahuje \(N\) medzerou oddelených celých čísel \(a_1, \dots, a_N\) (\(1 \le a_i \le 1\,000\,000\)).

V \(20\%\) vstupov bude platiť \(N \le 1500\).

V ďalších \(20\%\) vstupov, dostanete najviac \(1500\) rôznych čísel.

Na jediný riadok výstupu vypíšte jediné celé číslo, súčet najmenších spoločných násobkov čísel po dvojiciach modulo \(10^9+7\).

Príklady

Input:

2
40 32

Output:

392

Máme 4 dvojice čísel: \((40,40)\), \((40,32)\), \((32,40)\), \((32,32)\). Ich najmenšie spoločné násobky sú postupne: \(40\), \(160\), \(160\) and \(32\).

Input:

4
2 3 4 5

Output:

148