CF803F.Coprime Subsequences

Let's call a non-empty sequence of positive integers _a_1, _a_2... a__k coprime if the greatest common divisor of all elements of this sequence is equal to 1.

Given an array a consisting of n positive integers, find the number of its coprime subsequences. Since the answer may be very large, print it modulo 109 + 7.

Note that two subsequences are considered different if chosen indices are different. For example, in the array [1, 1] there are 3 different subsequences: [1], [1] and [1, 1].

我们称一个非空的正整数序列 $a_1, a_2, \dots, a_k$ 是互质的，当且仅当该序列中所有元素的最大公约数（GCD）等于 1。

给定一个由 $n$ 个正整数组成的数组 $a$，请计算其中互质子序列的个数。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

注意：若两个子序列所选取的下标不同，则认为它们是不同的子序列。例如，在数组 $[1, 1]$ 中，共有 3 个不同的子序列：$[1]$、$[1]$ 和 $[1, 1]$。

The first line contains one integer number n (1 ≤ n ≤ 100000).

The second line contains n integer numbers _a_1, _a_2... a__n (1 ≤ a__i ≤ 100000).

第一行包含一个整数 $ n $（$ 1 \leq n \leq 100000 $）。

第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \leq a_i \leq 100000 $）。

Print the number of coprime subsequences of a modulo 109 + 7.

输出数组 $a$ 的互质子序列个数对 $10^9 + 7$ 取模的结果。

In the first example coprime subsequences are:

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

In the second example all subsequences are coprime.

在第一个例子中，互质子序列有：

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

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