CF803F Coprime Subsequences

如果一个非空正整数序列 $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$ 2. $1,2$ 3. $1,3$ 4. $1,2,3$ 5. $2,3$ 在第二个样例中，所有子序列都是互质的。 由 ChatGPT 5 翻译