You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

​ 约瑟夫统帅着一个军队，军队里有$n$个人，第$i$个人的战斗力为$a_i$。约瑟夫称一些人$id_1...id_k$为一个团体，当且仅当$gcd(a_{id_1}...a_{id_k})>1$。一个团体的战斗力为$k*gcd(a_{id_1}...a_{id_k})$。

​ 现在约瑟夫想知道他的军队里所有可能的团体的战斗力之和，结果对$1,000,000,007(1e9+7)$取模。

【输入格式】

​ 输入文件名为army.in。

​ 第一行有一个数$n$，表示军队的人数。

​ 第二行有$n$个数$a_1...a_n$，表示每个人的战斗力。

【输出格式】

​ 输出文件名为army.out。

​ 输出仅一行，即为所有可能的团体的战斗力之和。

4
2 3 4 6

39

【样例解释】

​ 有$9$个团体，分别为$\{1\},\{2\},\{3\},\{4\},\{1,3\},\{1,4\},\{2,4\},\{3,4\},\{1,2,4\}$，战斗力分别为：$2,3,4,6,4,4,6,4,6$，故答案为$2+3+4+6+4+4+6+4+6=39$。

【样例2】

​ 见下发文件。

【数据范围】

​ 对于 $20\%$ 的数据，满足 $n \leq 10$。

​ 对于 $40\%$ 的数据，满足 $n \leq 2000,a_i \leq 2000$。

​ 另有 $20\%$ 的数据，满足所有的$a_i$都为质数。

​ 对于 $100\%$ 的数据，满足 $1 \leq n \leq 500000,1 \leq a_i \leq 500000$。