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 (10^9 + 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-----

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.


-----Output-----

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


-----Examples-----
Input
3
3 3 1

Output
12

Input
4
2 3 4 6

Output
39



-----Note-----

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

Difficulty: HARD
Tags: Number theory

Combinatorics

Dynamic programming

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
(n, N, MOD, ans) = (int(input()), int(1000000.0 + 5), int(1000000000.0 + 7), 0)
(cnt, pw, f) = ([0] * int(N), [1] * (n + 1), [0] * int(N))
for i in range(n):
	pw[i + 1] = pw[i] * 2 % MOD
for i in input().split():
	cnt[int(i)] += 1
for i in reversed(range(2, N)):
	t = sum([cnt[j] for j in range(i, N, i)])
	if t:
		f[i] = t * pw[t - 1] % MOD
		for j in range(i * 2, N, i):
			f[i] = (f[i] - f[j]) % MOD
		ans += i * f[i] % MOD
print(ans % MOD)


input()
a = list(map(int, input().split()))
(n, p) = (1000001, 1000000007)
cnt = [0] * n
curr = 1
for i in a:
	cnt[i] += 1
ans = [0] * n
tot = 0
for i in range(n - 1, 1, -1):
	k = sum(cnt[i::i])
	if k > 0:
		ans[i] = (k * pow(2, k - 1, p) - sum(ans[i::i])) % p
		tot = (tot + i * ans[i]) % p
print(tot)


n = int(input())
num = [0] * (1000000 + 1)
mx = 0
for i in input().split(' '):
	i = int(i)
	mx = max(mx, i)
	num[i] += 1
(f, p) = ([0] * (mx + 1), [0] * (mx + 1))
mod = 1000000000.0 + 7
p[0] = 1
for i in range(1, mx + 1):
	p[i] = 2 * p[i - 1] % mod
ans = 0
for i in range(mx, 1, -1):
	m = sum(num[i::i])
	if m:
		f[i] = (m * p[m - 1] % mod - sum(f[i::i])) % mod
		ans = (ans + f[i] * i) % mod
print(int(ans % mod))


n = int(input())
MAX = 1000005
mod = 1000000000.0 + 7
po2 = [0] * (n + 1)
po2[0] = 1
for v in range(1, n + 1):
	po2[v] = po2[v - 1] * 2 % mod
a = list(map(int, input().split()))
ta = [0] * MAX
for i in a:
	ta[i] += 1
cnt = [0] * MAX
for i in range(2, MAX):
	for j in range(i, MAX, i):
		cnt[i] += ta[j]
ans = [0] * MAX
for i in range(MAX - 1, 0, -1):
	if cnt[i] == 0:
		continue
	ans[i] = cnt[i] * po2[cnt[i] - 1] % mod
	for j in range(i + i, MAX, i):
		ans[i] = (ans[i] + mod - ans[j]) % mod
endans = 0
for v in range(2, MAX):
	endans = (endans + v * ans[v]) % mod
print(int(endans))


import sys
useless = sys.stdin.readline()
a = list(map(int, sys.stdin.readline().split()))
n = 1000001
mod = 1000000007
cnt = [0] * n
for i in a:
	cnt[i] += 1
arr = [0] * n
ans = 0
for i in range(n - 1, 1, -1):
	j = sum(cnt[i::i])
	if j > 0:
		arr[i] = (j * pow(2, j - 1, mod) - sum(arr[i::i])) % mod
		ans = (ans + i * arr[i]) % mod
sys.stdout.write(str(ans))


(n, m) = (int(input()) + 1, 1000001)
(d, s) = (1000000007, 0)
(t, c) = ([0] * m, [0] * m)
for i in input().split():
	c[int(i)] += 1
for i in range(m, 1, -1):
	k = sum(c[i::i])
	if k:
		t[i] = (k * pow(2, k - 1, d) - sum(t[i::i])) % d
		s += i * t[i]
print(s % d)