English · Original
Chinese · Translation
Formal · Original
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.
## 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 (109 + 7).
[samples]
## Note
In the first sample the clans are {1}, {2}, {1, 2} so the answer will be 1·3 + 1·3 + 2·3 = 12
北方的冬天已经来临，白 walkers 即将逼近。琼恩·雪诺拥有一支由 #cf_span[n] 名士兵组成的军队。当世界其他地方为铁王座而战时，他正为白 walkers 的进攻做准备。
他创造了一种方法来评估自己军队的强度。设第 #cf_span[i] 名士兵的强度为 #cf_span[ai]。对于某个 #cf_span[k]，若满足 #cf_span[i1 < i2 < i3 < ... < ik] 且 #cf_span[gcd(ai1, ai2, ..., aik) > 1]，则称序列 #cf_span[i1, i2, ..., ik] 为一个氏族。该氏族的强度定义为 #cf_span[k·gcd(ai1, ai2, ..., aik)]。他将军队的强度定义为所有可能氏族的强度之和。
你的任务是计算他军队的强度。由于结果可能非常大，你需要输出对 #cf_span[1000000007]（即 #cf_span[109 + 7]）取模的结果。
一个整数序列的最大公约数（gcd）是指能整除序列中每个元素的最大整数。
第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200000]）——军队的规模。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 1000000]）——表示士兵的强度。
输出一个整数——琼恩·雪诺军队的强度对 #cf_span[1000000007]（#cf_span[109 + 7]）取模的结果。
在第一个样例中，氏族为 #cf_span[{1}, {2}, {1, 2}]，因此答案为 #cf_span[1·3 + 1·3 + 2·3 = 12]。
## Input
第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200000]）——军队的规模。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 1000000]）——表示士兵的强度。
## Output
输出一个整数——琼恩·雪诺军队的强度对 #cf_span[1000000007]（#cf_span[109 + 7]）取模的结果。
[samples]
## Note
在第一个样例中，氏族为 #cf_span[{1}, {2}, {1, 2}]，因此答案为 #cf_span[1·3 + 1·3 + 2·3 = 12]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of soldiers.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i \in [1, 10^6] $.
A *clan* is a non-empty subset $ S \subseteq \{1, 2, \dots, n\} $ such that $ \gcd(\{a_i \mid i \in S\}) > 1 $.
The *strength* of a clan $ S $ is defined as $ |S| \cdot \gcd(\{a_i \mid i \in S\}) $.
**Constraints**
1. $ 1 \le n \le 200000 $
2. $ 1 \le a_i \le 1000000 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Compute the total strength of all clans:
$$
\sum_{\substack{S \subseteq \{1,\dots,n\} \\ S \neq \emptyset \\ \gcd(\{a_i : i \in S\}) > 1}} \left( |S| \cdot \gcd(\{a_i : i \in S\}) \right) \mod 1000000007
$$
API Response (JSON)
{
"problem": {
"name": "D. Winter is here",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF839D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "北方的冬天已经来临，白 walkers 即将逼近。琼恩·雪诺拥有一支由 #cf_span[n] 名士兵组成的军队。当世界其他地方为铁王座而战时，他正为白 walkers 的进攻做准备。\n\n他创造了一种方法来评估自己军队的强度。设第 #cf_span[i] 名士兵的强度为 #cf_span[ai]。对于某个 #cf_span[k]，若满足 #cf_span[i1 < i2 < i3 < ... < ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of soldiers. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i \\in [1, 10^6] $. \n\nA *clan* is a non-empty...",
"is_translate": false,
"language": "Formal"
}
]
}