#include <bits/stdc++.h>
///Base=100.000.000
///Val=1.000
///N=500
using namespace std;
///
int n, i, j, k, mx, add1;
int val[501], powers[501][25], ciur[1001], check[1001];
bitset<1001> ok;
long long res;
///
void read();
void solve();
void write();
void formPow(int i);
void diff(int i);
void sum(int i);
void buildCiur();
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("indep.in", "r", stdin);
    scanf("%d", &n);
    for(i=1; i<=n; ++i){
        int x;
        scanf("%d", &x);
        if(x==1) ++add1;
        val[i]=x;
        mx=max(mx, x);
        ++check[x];
    }
    fclose(stdin);
}
void solve(){
    powers[0][0]=powers[0][1]=1;
    for(i=1; i<=n; ++i) formPow(i);
    for(i=0; i<=n; ++i) powers[i][1]=powers[i][1]-i-1;
    buildCiur();
    for(i=2; i<=mx; ++i){
        if(ok[i]) continue;
        int tot=0;
        for(j=i; j<=mx; j+=i) tot+=check[j];
        if(ciur[i]&1) diff(tot);
        else sum(tot);
    }
    powers[0][0]=1;
    powers[0][1]=add1;
    sum(0);
}
void write(){
    freopen("indep.out", "w", stdout);
    printf("%d", powers[n][powers[n][0]]);
    for(i=powers[n][0]-1; i>=1; --i){
        for(j=10000000; j>=1; j/=10){
            printf("%d", (powers[n][i]/j)%10);
        }
    }
    fclose(stdout);
}
void formPow(int i){
    int j, r=0;
    powers[i][0]=powers[i-1][0];
    for(j=1; j<=powers[i][0]; ++j){
        powers[i][j]=r+2*powers[i-1][j];
        r=powers[i][j]/100000000;
        powers[i][j]%=100000000;
    }
    if(r) powers[i][++powers[i][0]]=r;
}
void diff(int i){
    int j;
    for(j=1; j<=powers[n][0]; ++j){
        powers[n][j]-=powers[i][j];
        if(powers[n][j]<0){
            powers[n][j]=100000000+powers[n][j];
            --powers[n][j+1];
        }
    }
    while(!powers[n][powers[n][0]] && powers[n][0]>1) --powers[n][0];
}
void sum(int i){
    int j, r=0;
    for(j=1; j<=powers[n][0]; ++j){
        powers[n][j]+=r+powers[i][j];
        r=powers[n][j]/100000000;
        powers[n][j]%=100000000;
    }
    if(r) powers[n][++powers[n][0]]=r;
}
void buildCiur(){
    for(i=2; i<=mx; ++i){
        if(ciur[i]) continue;
        for(j=i; j<=mx; j+=i){
            ++ciur[j];
            if(!(j%(i*i))) ok[j]=true;
        }
    }
}