集邮家 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 购买了第二张邮票,商店给了他第一张和第三张邮票作为礼物。