题目描述

给定一个数列 $a_{i}$，若子序列长度为 $k$，最大公约数为 $\gcd$，定义子序列的权值为 $k \times \gcd$。求所有 $\gcd > 1$ 子序列的权值和，答案对 $10^{9}+7$ 取模。

输入格式

第一行一个整数 $n$，$1\le n\le 200000$。

第二行 $n$ 个整数 $a_i$，$1\le a_{i}\le 1000000$。

输出格式

一个整数表示答案，对 $10^{9}+7$ 取模。

3
3 3 1

12

4
2 3 4 6

39