题目描述

如果一个非空正整数序列 $a_{1},a_{2},\ldots,a_{k}$ 的所有元素的最大公约数等于 $1$，那么称这个序列为「互质序列」。

给定一个长度为 $n$ 的正整数数组 $a$，请你求出其互质子序列的个数。由于答案可能非常大，请输出答案对 $10^{9}+7$ 取模后的结果。

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

输入格式

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

第二行包含 $n$ 个正整数 $a_{1},a_{2},\ldots,a_{n}$（$1\leq a_{i}\leq 100000$）。

输出格式

输出 $a$ 的互质子序列的个数，对 $10^{9}+7$ 取模。

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

5

输入输出样例 #2

输入 #2

4
1 1 1 1

输出 #2

15

输入输出样例 #3

输入 #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$

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

由 ChatGPT 5 翻译