#include <fstream>
#define X first
#define Y second
using namespace std;
ifstream fin("indep.in");
ofstream fout("indep.out");
int n,i,j,prim[510],k,v[510],d,x,sol,p,ok,e,maxim;
pair<int,int> w[1010];
int sir[510][510],nr,prod,par[510],imp[510];
void adunare(int A[], int B[], int C[]){
    int t=0;
    for(int i=1;i<=max(A[0],B[0]);i++){
        C[i]=A[i]+B[i]+t;
        t=C[i]/10;
        C[i]%=10;
    }
    C[0]=max(A[0],B[0]);
    if(t){
        C[++C[0]]=t;
    }
}
void scadere(int A[],int B[]){
    int t=0;
    for(int i=B[0]+1;i<=A[0];i++)
        B[i]=0;
    for(int i=1;i<=A[0];i++){
        A[i]=A[i]-B[i]-t;
        if(A[i]<0){
            t=1;
            A[i]+=10;
        }else
            t=0;
    }
    while(A[A[0]]==0)
        A[0]--;
}
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i];
        if(v[i]>maxim)
            maxim=v[i];
    }
    sir[0][0]=1, sir[0][1]=1;
    for(i=1;i<=n;i++){
        adunare(sir[i-1],sir[i-1],sir[i]);
        sir[i-1][1]--;
    }
    sir[n][1]--;
    for(i=2;i<=maxim;i++){
        x=i;
        j=2;
        ok=1;
        nr=0;
        while(x!=1){
            e=0;
            while(x%j==0){
                e++;
                x/=j;
            }
            if(e==1)
                nr++;
            if(e>=2)
                ok=0;
            j++;
        }
        if(ok){
            w[++k].X=i;
            w[k].Y=nr;
        }
    }
    imp[0]=par[0]=1;
    for(i=1;i<=k;i++){
        nr=0;
        for(j=1;j<=n;j++)
            if(v[j]%w[i].X==0)
                nr++;
        if(w[i].Y%2==1)
            adunare(imp,sir[nr],imp);
        else
            adunare(par,sir[nr],par);
    }
    scadere(imp,par);
    scadere(sir[n],imp);
    if(sir[n][0]<=0)
        fout<<"0";
    for(i=sir[n][0];i>=1;i--)
        fout<<sir[n][i];
    return 0;
}