for (int s = i;/*结束的条件先空着一会儿说*/; s = (s - 1) & i) {
//s是i的子集
int bu = i ^s;//bu是s在i中的补集
}

$$(x+y)^n=\sum {n \choose k}x^ky^{n-k}$$

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;
const ll MAXN = 400005;
const ll MOD = 1000000007;
ll n, a[MAXN], dp[MAXN], phi[MAXN], m, ma;//ma是a中的最大值，m是最大值的位数
ll prime[MAXN], pc;

void eulerTable(int x) {
phi[1] = 1;
for (int i = 2; i <= x; ++i) {
if (phi[i] == 0) {
prime[pc++] = i;
phi[i] = i - 1;
}
for (int j = 0; j < pc && prime[j] * i <= x; ++j) {
if (i % prime[j] == 0) {
phi[prime[j] * i] = prime[j] * phi[i];
break;
} else {
phi[prime[j] * i] = (prime[j] - 1) * phi[i];
}
}
}
}

int main() {
scanf("%lld", &n);
for (int i = 0; i < n; ++i) {
ll t;
scanf("%lld", &t);
a[t]++;
ma = max(ma, t);
}
while ((1 << m) <= ma) { m++; }
eulerTable(1 << m);
dp[0] = 1;
for (int i = 1; i <= (1 << m); ++i) {
for (int s = i;; s = (s - 1) & i) {
//s是i的子集
int bu = i ^s;//bu是s在i中的补集
if (s < bu) break;
dp[i] = (dp[i] + dp[bu] * a[s]) % MOD;
}
}
ll ans = 1;//加上空集
for (int i = 1; i <= (1 << m); ++i) {
ans = (ans + dp[i] * phi[i + 1]) % MOD;
}
for (int i = 0; i < a[0]; ++i) {
ans = ans * 2 % MOD;
}
printf("%lld\n", ans);
return 0;
}