CF839D Winter is here

北方的冬天已经来临，异鬼正在逼近。John Snow 拥有一支由 $n$ 名士兵组成的军队。当全世界都在为铁王座争斗时，他正在为异鬼的进攻做准备。 他发明了一种衡量军队强度的方法。设第 $i$ 位士兵的战斗力为 $a_i$。对于某个 $k$，他称 $i_1,i_2,\ldots,i_k$ 构成一个「氏族」，当且仅当 $i_1 < i_2 < \cdots < i_k$ 且 $\gcd(a_{i_1},a_{i_2},\ldots,a_{i_k}) > 1$。他将该氏族的强度定义为 $k \cdot \gcd(a_{i_1},a_{i_2},\ldots,a_{i_k})$。然后他将所有可能氏族的强度之和定义为军队的总强度。 你的任务是计算他的军队的总强度。由于答案可能非常大，请输出对 $1000000007$（$10^9+7$）取模后的结果。 一个整数序列的最大公约数（gcd）是使该序列中每个元素都能被其整除的最大整数。

第一行包含一个整数 $n$（$1 \leq n \leq 200000$）——军队的人数。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 1000000$）——分别表示每个士兵的战斗力。

输出一个整数，表示 John Snow 的军队的总强度，对 $1000000007$ 取模后的结果。

在第一个样例中，所有的氏族为 $\{1\},\{2\},\{1,2\}$，因此答案为 $1 \cdot 3 + 1 \cdot 3 + 2 \cdot 3 = 12$。 由 ChatGPT 5 翻译