CF 803F / Mobius Function

/***
 created: 2023-01-11-23.19.07
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define all(we) we.begin(),we.end()
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define nl '\n'

const ll mod=1e9+7;
#define maxN 100007
int mob[maxN];
bool mark[maxN];
void mobius()
{
    ll i, j;
    for(i = 0; i < maxN; i++) mob[i] = 1;
    for(i = 2; i < maxN; i++)
    {
        if(!mark[i])
        {
            mob[i] *= -1;
            for(j = i + i; j < maxN; j += i)
            {
                mark[j] = true;
                mob[j] *= j % (i * i) ? -1 : 0;
            }
        }
    }
}

ll bigmod(ll a,ll c,ll d)
{
    if(c==0) return 1LL;
    ll x=bigmod(a,c/2,d);
    x=(x*x)%d;
    if(c%2==1LL)
    {
        x=(x*a)%d;
    }
    return x;
}

ll c[maxN];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    mobius();

    ll n,m,i,j,k,l;

    cin>>n;

    for(i=0;i<n;i++)
    {
        cin>>m;
        c[m]++;
    }

    ll ans=0;

    for(i=1;i<maxN;i++)
    {
        k=0;
        for(j=i;j<maxN;j+=i)
        {
            k+=c[j];
        }

        ans+=((mob[i]*(bigmod(2,k,mod)-1+mod)%mod)+mod)%mod;
        ans%=mod;
    }

    cout<<ans<<nl;

    return 0;
}