### 问题描述 约瑟夫统帅着一个军队，军队里有 $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)$ 取模。 ### 输入格式 第一行有一个数 $n$，表示军队的人数。 第二行有 $n$ 个数 $a_1...a_n$，表示每个人的战斗力。 ### 输出格式 输出仅一行，即为所有可能的团体的战斗力之和。 ### 输入样例 ``` 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$。 ### 数据范围 对于 $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$。