Winter is here
Contest: Codeforces Round 428 (Div. 2)
Difficulty rating: 2200
Tags: combinatorics, dp, math, number theory

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 ai. For some k he calls i1, i2, ..., ik a clan if i1 < i2 < i3 < ... < ik and gcd(ai1, ai2, ..., aik) > 1 . He calls the strength of that clan k·gcd(ai1, ai2, ..., aik). 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.

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

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000000) — denoting the strengths of his soldiers.

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
3
3 3 1

Example output:
12

Example input:
4
2 3 4 6

Example output:
39

Editorial:
1st method:
Let cnt[i] be the number of such js that aj is divisible by i. Also let p[i] be i-th prime number.
Let f(m) be $$\sum_{x \subseteq S} size(x)$$ for an arbitrary set with m members(something like the sum of strengths of all possible subsets, but replace 1 with the gcd of the sequence)
Finally let ans[i] be the sum of strengths of clans which gcd(strengths - of - clan’s - soldiers) = i.
Now we can calculate ans[i] by “Inclusion–exclusion principle” :
$$$$
Because i·f(i) includes all possible clans that their members are all multiples of i, not the ones with gcd equal to i .Now, we can do the above calculation by a “foor-loop” through the multiples of i.
So all we have to do , is to calculate f(x) very fast. Actually f(x) = x·2x - 1 because :
$$f(x) = \sum_{i=0}^{x} i \cdot \binom{x}{i} = x \cdot 2^{x-1}$$
2nd method:
Let cnt[i] be the number of such js that aj is divisible by i. Than cnt[i] is count of soliders with strength of i, 2i, 3i, ....
Let ans[i] be count of people in clans with gcd = i. To find ans[i] let's understand, how to find count of people in clans, in which every number is divided by i. If cnt[i] = c, it's
$$1 \cdot {c \choose 1} + 2 \cdot {c \choose 2} + \ldots + c \cdot {c \choose c} = \frac{1 \cdot c!}{(c-1)! \cdot 1!} + \frac{2 \cdot c!}{(c-2)! \cdot 2!} + \ldots + \frac{c \cdot c!}{0! \cdot c!} = \frac{c!}{(c-1)! \cdot 0!} + \frac{c!}{(c-2)! \cdot 1!} + \ldots + \frac{c!}{0! \cdot (c-1)!} = c \cdot {c-1 \choose 0} + c \cdot {c-1 \choose 1} + \ldots + c \cdot {c-1 \choose c-1} = c \cdot 2^{c-1}$$
Let's calculate ans[i] from the end. Then ans[i] = cnt[i]·2cnt[i] - 1 - ans[2i] - ans[3i] - ....
Answer for problem's question is $$\sum_{i=2}^{1000000} i \cdot ans[i]$$.
Asymptotics of solution is $$O(k + \frac{k}{2} + \frac{k}{3} +...) = O(k \cdot log_k)$$, where k is maximal value of ai.