CF839D.Winter is here

Winter is here at the North and the White Walkers are close. John Snow has an army consisting of n soldiers. While the rest of the world is fighting for the Iron Throne, he is going to get ready for the attack of the White Walkers.

He has created a method to know how strong his army is. Let the i-th soldier’s strength be a__i. For some k he calls _i_1, _i_2, ..., i__k a clan if _i_1 < _i_2 < _i_3 < ... < i__k and gcd(_a__i_1, _a__i_2, ..., a__i__k) > 1 . He calls the strength of that clan k·gcd(_a__i_1, _a__i_2, ..., a__i__k). Then he defines the strength of his army by the sum of strengths of all possible clans.

Your task is to find the strength of his army. As the number may be very large, you have to print it modulo 1000000007 (109 + 7).

Greatest common divisor (gcd) of a sequence of integers is the maximum possible integer so that each element of the sequence is divisible by it.

寒冬已至北境，异鬼大军迫在眉睫。琼恩·雪诺拥有一支由 $n$ 名士兵组成的军队。当世人都在为铁王座而战时，他却正为抵御异鬼的进攻而厉兵秣马。

他设计了一种方法来评估自己军队的实力。设第 $i$ 名士兵的力量值为 $a_i$。对于某个整数 $k$，若下标序列 $i_1,\,i_2,\,\dots,\,i_k$ 满足 $i_1 < i_2 < i_3 < \dots < i_k$，且 $\gcd(a_{i_1},\,a_{i_2},\,\dots,\,a_{i_k}) > 1$，则称其为一个“氏族”（clan）。该氏族的强度定义为 $k \cdot \gcd(a_{i_1},\,a_{i_2},\,\dots,\,a_{i_k})$。琼恩将整支军队的强度定义为所有可能氏族的强度之和。

你的任务是计算这支军队的强度。由于结果可能非常大，请将答案对 $1000000007$（即 $10^9 + 7$）取模后输出。

一个整数序列的最大公约数（$\gcd$）是指能整除该序列中每个元素的最大正整数。

The first line contains integer n (1 ≤ n ≤ 200000) — the size of the army.

The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 1000000) — denoting the strengths of his soldiers.

第一行包含一个整数 $n$（$1 \leq n \leq 200000$）—— 表示军队的规模。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 1000000$）—— 表示士兵们的战斗力。

Print one integer — the strength of John Snow's army modulo 1000000007 (109 + 7).

输出一个整数——琼恩·雪诺军队的实力对 $1000000007$（即 $10^9 + 7$）取模的结果。

In the first sample the clans are {1}, {2}, {1, 2} so the answer will be 1·3 + 1·3 + 2·3 = 12

在第一个样例中，部族为 $\{1\},\ \{2\},\ \{1,\ 2\}$，因此答案为 $1\cdot3\ +\ 1\cdot3\ +\ 2\cdot3\ =\ 12$