← 返回题目列表

Codeforces · 585/E

E. 送给集邮家维塔利克的礼物

中文机器翻译题面 查看原题

集邮家 Vitalik 今天生日!

由于他是一家名为“Robin Bobin”的邮票商店的常客,商店管理层决定为他制作一份礼物。

Vitalik 想要购买一张邮票,商店会给他一组非空的剩余邮票,这样他们给他的邮票价格的最大公约数 (GCD) 就大于 1。如果购买的邮票价格与现有邮票套装的价格的 GCD 等于 1,那么 Vitalik 就会心满意足地离开商店。

商店管理层要求您计算 Vitalik 会完全满意地离开商店的不同情况的数量。由于所需的情况数量可能非常大,因此您需要找到该数字模 109 + 7 的余数。如果 Vitalik 购买的邮票不同,或者其中一套包含另一套不包含的邮票,则情况会有所不同。

输入

输入的第一行包含整数 n (2 ≤ n ≤ 5·105) — 可在“Robin Bobin”商店出售的不同邮票的数量。

第二行包含整数序列 a1, a2, ..., an (2 ≤ ai ≤ 107),其中 ai 是第 i 张邮票的价格。

输出

打印一个整数 — 所求情况数模 109 + 7 的余数。

示例

输入 #1

3
2 3 2

输出 #1

5

输入 #2

2
9 6

输出 #2

0

注意

在第一个示例中,可能出现以下情况:

- Vitalik 购买了第一张邮票,商店送给他第二张邮票作为礼物;
- Vitalik 购买了第三张邮票,商店给了他第二张邮票作为礼物;
- Vitalik 购买了第二张邮票,商店送给他第一张邮票作为礼物;
- Vitalik 购买了第二张邮票,商店送给他第三张邮票作为礼物;
- Vitalik 购买了第二张邮票,商店给了他第一张和第三张邮票作为礼物。