← 返回题目列表

Codeforces · 803/F

F. 互质子序列

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

如果正整数 a1, a2...ak 的非空序列所有元素的最大公约数等于 1,则该序列称为互质。

给定一个由 n 个正整数组成的数组 a,找到其互质子序列的数量。由于答案可能非常大,因此将其打印为 109 + 7 模。

请注意,如果选择的索引不同,则两个子序列被视为不同。例如,数组 [1, 1] 中有 3 个不同的子序列:[1]、[1] 和 [1, 1]。

输入

第一行包含一个整数 n (1 ≤ n ≤ 100000)。

第二行包含n个整数a1, a2... an (1 ≤ ai ≤ 100000)。

输出

打印模 109 + 7 的互质子序列的数量。

示例

输入 #1

3
1 2 3

输出 #1

5

输入 #2

4
1 1 1 1

输出 #2

15

输入 #3

7
1 3 5 15 3 105 35

输出 #3

100

注意

在第一个示例中,互质子序列是:

1. 1
2. 1, 2
3. 1, 3
4. 1, 2, 3
5. 2, 3

在第二个示例中,所有子序列都是互质的。