← 返回题目列表

Codeforces · 839/D

D. 冬天来了

中文机器翻译题面 查看原题

北方的冬天已经来临,异鬼即将来临。约翰·斯诺有一支由 n 名士兵组成的军队。当世界其他地方都在争夺铁王座时,他却要为异鬼的进攻做好准备。

他创造了一种方法来了解他的军队有多强大。设第i个士兵的力量为ai。对于某些 k,如果 i1 < i2 < i3 < ... < ik 且 gcd(ai1, ai2, ..., aik) > 1 ,他将 i1, i2, ..., ik 称为部落。他称该氏族的力量为k·gcd(ai1, ai2, ..., aik)。然后他通过所有可能氏族的力量总和来定义他的军队的力量。

你的任务是找出他的军队的实力。由于数字可能非常大,因此您必须以 1000000007 (109 + 7) 为模来打印它。

整数序列的最大公约数 (gcd) 是最大可能的整数,以便序列的每个元素都可以被它整除。

输入

第一行包含整数 n (1 ≤ n ≤ 200000) — 军队的规模。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 1000000) – 表示他的士兵的实力。

输出

打印一个整数——约翰·斯诺军队的兵力以 1000000007 (109 + 7) 为模。

示例

输入 #1

3
3 3 1

输出 #1

12

输入 #2

4
2 3 4 6

输出 #2

39

注意

在第一个示例中,氏族为 {1}、{2}、{1, 2},因此答案为 1·3 + 1·3 + 2·3 = 12