CF585E.Present for Vitalik the Philatelist

Vitalik the philatelist has a birthday today!

As he is a regular customer in a stamp store called 'Robin Bobin', the store management decided to make him a gift.

Vitalik wants to buy one stamp and the store will give him a non-empty set of the remaining stamps, such that the greatest common divisor (GCD) of the price of the stamps they give to him is more than one. If the GCD of prices of the purchased stamp and prices of present stamps set will be equal to 1, then Vitalik will leave the store completely happy.

The store management asks you to count the number of different situations in which Vitalik will leave the store completely happy. Since the required number of situations can be very large, you need to find the remainder of this number modulo 109 + 7. The situations are different if the stamps purchased by Vitalik are different, or if one of the present sets contains a stamp that the other present does not contain.

哲学家维塔利克今天过生日！

由于他是名为“罗宾·博宾”的邮票店的一位常客，该店管理层决定送他一份礼物。

维塔利克打算购买一枚邮票，而商店将额外赠送他一个非空的剩余邮票集合，使得所赠邮票价格的最大公约数（GCD）大于 1。若所购邮票的价格与所赠邮票集合中所有邮票价格的 GCD 恰好等于 1，则维塔利克将完全满意地离开商店。

商店管理层请你计算：维塔利克完全满意地离开商店的不同情形总数。由于该数目可能非常大，请你输出其对 $10^9 + 7$ 取模的结果。
两种情形被视为不同，当且仅当：维塔利克所购邮票不同，或两个赠送集合中至少有一个邮票属于其中一个集合但不属于另一个集合。

The first line of the input contains integer n (2 ≤ n ≤ 5·105) — the number of distinct stamps, available for sale in the 'Robin Bobin' store.

The second line contains a sequence of integers _a_1, _a_2, ..., a__n (2 ≤ a__i ≤ 107), where a__i is the price of the i-th stamp.

输入的第一行包含一个整数 $ n $（$ 2 \leq n \leq 5 \cdot 10^5 $）——表示“罗宾·博宾”商店中可供出售的不同邮票的数量。

第二行包含一个整数序列 $ a_1, a_2, \dots, a_n $（$ 2 \leq a_i \leq 10^7 $），其中 $ a_i $ 表示第 $ i $ 张邮票的价格。

Print a single integer — the remainder of the sought number of situations modulo 109 + 7.

输出一个整数——所求情况数对 $10^9 + 7$ 取模后的余数。

In the first sample the following situations are possible:

• Vitalik buys the 1-st stamp, the store gives him the 2-nd stamp as a present;
• Vitalik buys the 3-rd stamp, the store gives him the 2-nd stamp as a present;
• Vitalik buys the 2-nd stamp, the store gives him the 1-st stamp as a present;
• Vitalik buys the 2-nd stamp, the store gives him the 3-rd stamp as a present;
• Vitalik buys the 2-nd stamp, the store gives him the 1-st and 3-rd stamps as a present.

在第一个样例中，以下情况是可能的：

• Vitalik 购买了第 1 枚邮票，商店赠送他第 2 枚邮票；
• Vitalik 购买了第 3 枚邮票，商店赠送他第 2 枚邮票；
• Vitalik 购买了第 2 枚邮票，商店赠送他第 1 枚邮票；
• Vitalik 购买了第 2 枚邮票，商店赠送他第 3 枚邮票；
• Vitalik 购买了第 2 枚邮票，商店赠送他第 1 枚和第 3 枚邮票。