CF585E Present for Vitalik the Philatelist

今天是邮票收藏家 Vitalik 的生日！ 由于他是“Robin Bobin”邮票店的常客，店家决定送他一个礼物。 Vitalik 想购买一张邮票，店家会将剩下的邮票中的非空子集作为赠品送给他，条件是这些赠品邮票的价格的最大公约数大于 $1$。如果所购邮票的价格与赠品邮票集合的价格的最大公约数为 $1$，Vitalik 将会非常满意地离开商店。 现请你计算，有多少种不同的情况能够让 Vitalik 非常满意地离店。由于答案可能非常大，请输出该数对 $10^{9}+7$ 取模的结果。两种情况不同，是指 Vitalik 买的邮票不同，或者赠品集合中有些邮票彼此不同。

输入的第一行包含一个整数 $n$（$2\leq n\leq 5 \cdot 10^{5}$），表示“Robin Bobin”商店中待售的不同邮票数量。 第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$（$2\leq a_i\leq 10^7$），其中 $a_i$ 表示第 $i$ 张邮票的价格。

输出一个整数，表示令 Vitalik 满意离店的所有情形数对 $10^9+7$ 取模的结果。

在第一个样例中，有如下几种情况： - Vitalik 购买第 1 张邮票，商店赠送第 2 张邮票； - Vitalik 购买第 3 张邮票，商店赠送第 2 张邮票； - Vitalik 购买第 2 张邮票，商店赠送第 1 张邮票； - Vitalik 购买第 2 张邮票，商店赠送第 3 张邮票； - Vitalik 购买第 2 张邮票，商店赠送第 1 张和第 3 张邮票作为礼品。 由 ChatGPT 5 翻译